Hi Tom,
I've always reg'd my UK domains with 123-Reg and despite hearing others complaint of their support I've always found them really good.
The main things to be concerned about are their help/support times for if/when you need it, then other things to look for are how easy their control panel is to use, 123-Reg is very simple compared with GoDaddy for example. Other than that it's down to price I guess, everyone has different experiences with the big domain registrars so I think you can probably find positive/negative reviews of each one. Whilst I reg my domains with 123-Reg I'd never host with them.
Hope that helps in someway, Greg.