I just did this and followed the codex by the letter and had problems. There are actually two different sets of instructions on the codex, mostly similar but a little different. I'm sorry, I dont remember which one got me closer - I think it's the one that was linked under 'wp back up week'. it's got inline images with numbers.
Anyway, the main problem I had was the version of sql on the new server was older and kept running into problems importing the database on the new server because of character encoding lines. Changing the export compatability options to an older version of sql stripped it of those lines and all was swell. If that doesn't make sense now, dont worry. it will when you're on the export screen. just follow the codex and if doesn't work, try it again, changing the compatability to an older version of sql.