Thanks for your post.
It sounds like you're doing everything correctly, so it's a little odd. The first thing I'd try is going into your profile page and generating a new API key:
If that still doesn't work, are you running VS under a different user account to the one you log into DM with? This shouldn't really matter AFAIK (for instance I'm running VS as administrator and DM as myself and it still works) but it /may/ be relevant...?
The VS Addin also creates a logfile in C:\\Users\\<your username>\\AppData\\Local\\Red Gate\\Deployment Manager VS Extension which could also be worth looking at (feel free to email email@example.com
if you'd rather not use the forum!)