Which version Windows 7 Home Premium do you have?
A few possible reasons why it does not work.
UK uses Windows 7 Home Premium N, not Home Premium. N just lacks media player.
If the OS is Home Premium and not Home Premium N, that could be a reason why it won't upgrade since the non N isn't made for the UK.
2nd, that key has been upgraded to Win8, so it can't be used again to upgrade to Win7 Ultimate.
Besides upgrading from Win7 Home Premium to Ultimate is a waste of money.
Both OS are exactly the same, all Ultimate has is just Bitlocker, Domain Support, and other features most home users will probably never use. The only advantage between Ultimate and Home Premium is larger memory and dual CPU support. 16GB max for Win7 Home Premium 64bit vs 192GB max for Win7 Ultimate 64bit.
Since that key has been upgraded to Win8, then install Win8 and do a free upgrade to Win8.1.
Here is a Win7 comparison chart
http://en.wikipedia.org/wiki/Windows_7_editions