Move to a UK Host as soon as possible. I moved my .com from US to UK hosting around six weeks ago and the transition went very smoothly indeed. Before the move my site had been firmly stuck at #3, but only when doing a 'normal' web search. It also did not appear when selecting 'pages from the UK' ... even when using the site: command.
Within 48 hours of moving to UK hosting, both Google and MSN UK began to list the site when selecting 'uk results'. As an added bonus, I'm at #2 in the UK SERPs.
Moreover, if you use a good UK host, your visitors will likely see a slight improvement in how fast your site loads.