Occam's Razor nearly always applies when troubleshooting technology issues!
If anyone has been helpful to you, please show your appreciation by clicking the button inside of their post. Please click here and read, along with the threads to which it links, for helpful information to guide you as you proceed. I always recommend that you treat your BlackBerry like any other computing device, including using a regular backup schedule...click here for an article with instructions.
This might seem like an obvious thing to try , but I was having the same problem, after setting up a yahoo account with no trouble i got the same message trying to set up gmail. All I did was to set up gmail under "other" accounts on the wizard and it set up first time.