(I had to refresh my memory of the thread and check a couple of things).
Let's recap on what I understand is your situation.
You purchased this machine with Home Premium installed.
At some point, you purchased an Upgrade to Ultimate.
All Upgrades are Retail pretty much by definition - the only exceptions are a) the Free Upgrades from Vista for machines bought immediately before and after the launch of Windows 7, and b) Upgrades installed before they leave the factory.
Was this an Anytime Upgrade, or a full Upgrade with discs and a box?
What happens if you attempt validation at
www.microsoft.com/genuine/validate ? It may give some more information, or give another error message that is more meaningful that what we currently have.
I mis-spoke earlier when I said that you needed to use the Key from the COA sticker on the machine - you need to use the Key from the Upgrade box, or from the AU package (the Key on the COA sitcker will only work for Home Premium) using the
SLUI 3 command.
If that fails (make sure that you're using the right one), then I can see no reason why
SLUI 4 shouldn't work with the existing Key, so that you can at least talk to an operator with an activation code to hand.
If it doesn't work, then I can only suggest that you try contacting your local Volume Activation Center for assistance - they are for Volume licenses, but will assist if you ask nicely
Microsoft Volume Licensing - Activation Centers