The error message your getting is by design I think. In order to logon via wireless like your wanting you must first log into the domain (via network cable) so the cached account will be created. When you try it with a new user it will not work because that computer knows it has never attempted to log on locally with those new user credentials so it wants to look for the domain to validate the id/password thus creating a cached domain account on that computer. So after that you reboot the computer then attempt to log in via wireless and it works like you said.
There may be a way around this. If so I do not know how. If someone knows I'd like to know too!
Hope this helps.