Weirdness... I just switched from the internet2 APN to the wap APN (no proxy or anything) and it Just Works. What's more, my EDGE speed went from 30-40kpbps to about 100kbps (same exact location/signal strength/etc., Upper West Side Manhattan NYC).
Edit: Never mind, I think it's just intermittent. Seems to change every time I run it.