Mine's registered - along with my AppleCare for it.
Double check your serial number is correct. Are you getting it from the box or from the Unit itself?
Like the message says you may be mixing up letters and numbers such as zeroes and the O, or maybe a 1 and an l.
If you still can't get it to work, call Apple Support. You get 90 days free phone support, so why not make use of it.