I used to use UKReg, but fasthosts suck (they own UKReg). UKReg lacks some nice features, the billing system is retarded and the management interface is a ball-ache in general. I use
Yahoo! small business domains now. They let you manage your A records, subdomains, MX records, etc. I would always choose a reliable DNS provider that lets you manage these things rather than going for some budget package included with hosting. It makes things much, much easier if you want to change web hosts, email providers, etc. Another advantage of Yahoo! is that they let you delegate subdomains. This means that I can have a subdomain set up that resolves to a dyndns domain, combined with the dyndns feature on my home router means that I have a
subdomain of my own domain name pointing to my home IP that auto updates itself...
A word of warning about registering domains, don't go typing your desired domain name into random availability checking websites or you may find that it gets conveniently registered on your behalf, then sold back to you at a premium.