I also had issues syncing Gmail, but a bit different than previously described. (A little background...) I had an HTC Arrive a few months back. I synced my Gmail contacts, calendar and email no problem. I updated the phone to Mango and everything was still fine. I decided to sell the phone and switch back to my Evo. A few months pass and I recently got the itch to have an Arrive again so I bought a used one yesterday that came with Mango pre-installed. Long story short, the phone would not let me sync Gmail at all. If I selected "Google" from the list of available accounts to sync, it kept giving me errors. (ironically, it didn't give me a reason for the error, it just said "Attention Required" next to the account name and if I pressed the sync button, the error said something like update failed, please try again later, error # blah blah blah (8 something). I was able to sync my email ONLY by entering my Gmail info as an "Other Account" but this didn't help contacts or my calendar. This also didn't allow me to set receive "items as they arrive". I spent an hour on the phone with Sprint and they claimed it was a Mango issue (rep claimed to find this info on an HTC website). I inquired about a possible downgrade back to NODO since I didn't have previous problems syncing Gmail and the rep was going to transfer me to someone else to "look into that". I then gave up and put the phone down for the night and hung up. I was about to use an alternate way to load the contacts today when I decided to play around with the phone a little more first. I REALLY wanted my contacts and calendar syncing properly in Gmail since I switch phones often and I find that more convenient than switching services. It turns out if I deselected "contacts" from the sync option under "Google Account" on the phone, then it synced my calendar and email. I then went to my Gmail account on the computer and before exporting my contacts, I decided to look at a few of them and I noticed some people had birthdays listed like "January 8, 1". I decided to fix the "1" to "1980" or whatever correct year and sure enough I went back to my phone, selected "sync contacts" and it did no problem! I know this isn't completely relevant to the OP's thread, but this is one of the first threads that popped up when I Googled the issue. Hopefully listing this here can help someone else who has the same issue.
On a side note, my Windows Live account has shown "attention required" on both of my Arrives. It claims my password is incorrect when it is not. I'm able to access my Xbox avatar and the Marketplace, etc without a problem.