In many cases this is because someone is lingering on the server. You could go through the process of figuring out who's logged on and asking them to log out, or kick them from the server. But there's another way.
It's possible to remotely connect to the physical console session on the server (also known as session 0). If someone is already using the console session, you'll learn who's connected and will be asked if you want to disconnect them. Since this feature is only intended for ninja hackers, you'll have to run this from command line.
On Windows 7/2008 Server:
mstsc.exe /admin /v:yourservernameOn Windows 2003 server:
mstsc.exe /console /v:yourservernameYou probably figured out that the command switches /admin and /console did the trick here. A word of advice, don't share this with your co-workers, you want to keep the console session to your self!
The /admin and /console switches are described in Microsoft's article on changes to remote administration in Windows Server 2008. Also, if you're running Windows Server 2003 or Windows XP it's possible to upgrade to Terminal Services Client 6.0 to get the new and shiny features offered by Remote Desktop on Vista and later.