I'm writing this in case this happens to me again. Today, I was having issues remoting into a Windows Server 2003 server. It was complaining about lack of rights, and that I should be a member of the Remote Desktop Users group to have those rights. Sounds great, but my user was already a member of that group. Doing some Googling I came across this process.
Start -> Run -> Secpol.msc
Click user rights assignments
Right click allow logon through terminal services and click 'properties'
Sure enough, my user was not in this group. Adding the user, and everything is working. Odd thing, it just stopped working all of a sudden.