Google maps has been the bee's knees for me since it first came out. Periodic updates have made it better. If you have uninstalled it and reinstalled it, you have the latest version. Are you receiving e-mails reliably? Are you able to browse to lots of sites?
Are you on a BES server where there may be a policy restricting this particular kind of traffic? What about the built-in firewall? Perhaps your BlackBerry isn't allowing the trafffic...?