Hi Daniel,

I had the same issue today. I couldn't connect via 2G and 3G. Only Wi-Fi worked. I tried everything you wrote about. But after doing the following steps, my N900 lost and I finally won :-)
Go to "settings" - "internet connections" - "connections" ... then choose your provider's connection - click "edit" and then always push the "next" button until it's finished.
Now try connecting again. In my case it worked again and I hope, this fits yours too.

greets,
N(9)00bie