I registered my primary domain through A Small Orange, which hosts my websites. I am pretty sure they resell Godaddy registrations. My second domain (ASO will only register one, unfortunately) is through Namecheap. Each of those registrations is about $10 / year. I don't know if either of them takes PayPal, but they're the cheapest I've seen so far, and I haven't had any troubles with them.