The specific problem I am having is that trying to watch videos directly from youtube.com (non mobile, regular version) will rarely work over EVDO for me.
Regardless of the speed I get.
Google Videos works fine though, even when linking to Youtube videos.

Using Wi-Fi I have no problems.

Occasionally EVDO youtube.com (again the non mobile version) will work.

When it doesn't work, Pocket Internet Explorer freezes for anywhere form 10 seconds to about 20 seconds, sometimes a bit longer.