It appears that I'm the only one with this issue (judging by the lack of responses)? So it must be something very specific... This week I gave it another try and did the following:
1) Upgraded FW to 1.0.04.12210 - still the same, didn't help
2) Tried multiple GMail accounts (both @gmail and Google Apps) - all fail the same way
3) Tried to connect to another WiFi router in the office - fails the same way
All I can think of trying now is to do some "factory reset" of the device...
UPDATE: "Restore Defaults" didn't help, but I just found out a separate thread was started to discuss the issue so I'll just move there.