Well, I finally saw the light and cancelled by Sky Subscription, and purchased a Sony VTX-D800 Freeview box. So far I'm very impressed with the Picture Quality and software.
I connected it up to my TiVo (aerial -> TiVo -> STB) as stated in the manual, but it couldn't find BBC1 or BBC2 plus a few other channels. So I swapped the STB and TiVo around and it picked up all the channels without problem! Is there a problem with my TiVo? I searched the forums and there was a similar topic, to actually insert the aerial into the STB rather than the TiVo. OK...
So I re-ran the Setup Guide, and when it came to testing the Channel changing/IR, nothing worked! The screen is blank apart from the TiVo text. When I pressed 'AUX', the channel had changed correctly. So it seems that the channels do change - it's just that I can't see it happening in the Setup.
You should always have the aerial pass through the STB first. The more links in the chain, the weaker/noisier the signal is likely to get (and on a digital receiver, that's bad news!).
Some things to check: have you configured TiVo to use your STB for the channels you receive (if I remember correctly, you should select the CAB channels instead of the AER ones)? Have you not perhaps selected the same channel twice in a row (e.g. you're already on BBC2, and you press "2" on the remote)?
There is a bug on TiVo where sometimes it doesn't pick up the feed from the auxiliary input even though it's clearly there. It might be that, although I've only experienced it a handful of times.
My Sony VTX-D800 has been running fine since the beginning of the year. No complaints (except for the shared channel issue that can leave your recording with the grey mist or that annoying BBC retune message).