In Windows server 2008, it is technically possible for you to specify different values for the UPN and the NetBIOS username. Check the UPN and see what you get. Ensure it is correct (and set), and see what you get.
You can specify a UPN a number of ways, also. You can specify user@subdomain, firstname.lastname@example.org, and email@example.com. For instance, if you have a domain registered to your organization example.com, your domain's NetBIOS name would be EXAMPLE by default; some organizations may configure it EXAMPLECOM. You would normally specify, in this case, EXAMPLECOM\username but also firstname.lastname@example.org.
It may also be that your RDP target cannot contact the DC, so it can't resolve the UPN, but if it has cached credentials for the NB username, it will still take that.