What 3rd party apps do you use for gmail? I can't get a blackberry plan where I live... and the legit gmail app depends on it. I'm currently just using the Opera browser to hit gmail.com's mobile site, and that works okay, but not great. I've also tried flurry, but that app is very basic.

Those are actually the only choices I know of... push email, and the gmail application.

I thought the gmail application would work without a BlackBerry Data Plan.

Nah, I downloaded it while I was in the states and whenever I try to connect, it tells me that I need a data connection...which I do, just not the bb one :P

do you have TCP settings configured? I don't know what they would be for your carrier... but:
Options > Advanced > TCP.

What is there?