So far I've had Gandi and DNSimple recommended, with Gandi getting the most votes. I've also been asked what my problem with 123-reg is, but it wouldn't fit into 140 characters, so I thought I'd branch it to here.
Their control panel is appalling, and not just because of the fridge-magnet typography. Here's a message that I get at the top of my 123-reg control panel...
<img src="dl.dropbox.com />
Apparently all my domain name(s) will soon expire! I better click on that! Unfortunately it takes me to a blank page. This attention to quality doesn't give me much confidence in their attention to security.