I discovered this problem on my iPhone too and it's annoying. Fix it Apple! Changing my Airport Express settings each time isn't an option.
Currently, the wireless network is set to G-Only since this was the best setup for our office. It was only when I switched the Wireless Network Mode to B-Only that YouTube videos began watchable again. None of the other settings had any effect.