Two things:
Have you bought Minecraft? (I assume that you did, because you would get a User not premium, if you hadn't, as far as I know)
How good would you yourself estimate your internet connection? Can you play any other games without lagging?
WARNING: I have not tried the thing I quote now, because I do not have any issues with my Minecraft or any servers, so you should make a backup of the hosts file before editing anything in it.
Might as well quote something from
www.minecraftforum.net :
if you are still having this problem, you need to check your hosts file.
go to start > run
type in 'notepad %windir%\system32\drivers\etc\hosts' (without the quotes)
look for a line with 'minecraft.net' or '
www.minecraft.net' and remove it & save the hosts file.
restart minecraft and you should be able to connect to servers.
It's this post:
http://www.minecraftforum.net/topic/114317-failed-to-verify-username/