Ian Morrish's WSSDemo Blog
User already exists!
http://www.wssdemo.com/blog/Log/DisplayLog.aspx?ID=171

I know some people get very frustrated by this error when you try and add some to a SharePoint site who’s Windows account was recreated.
 
Even though you delete their old account from a SharePoint site, you can’t add them back. You need to also delete them from the “Manage Site Collection Users” which can be found at the following URL  /_layouts/1033/siteusrs.aspx

Via FeedShow.com