I think the issue is the usual problem with user interfaces, in that they often try to be all things to all people. DNS is complicated, and many people don't fully understand its full subtleties (myself most certainly included). Part of the problem is that the DNS protocol itself is designed to be generic and extensible - essentially it's just a distributed database. The uses to which it's put, however, have many more constraints upon it, and that's where the complexity arrives.
I don't believe one interface can successfully appeal to people who don't really understand DNS and just want a few A records and CNAMEs, and also to a power user who wants to create arbitrary TXT and SRV records. Therefore, I think providers should either pick one target market or the other, or offer two different interfaces - so you start simple, but can switch to "advanced mode" at your own risk.
The "simple mode" would be a "wizard" interface, where you select from a few limited options, and the user could be prompted by plain language questions asking what they're trying to do. This would have the advantage that adding obscure records for SPF or Google domain validation or similar could be written in as specific "macros" which do the right thing. The downside is, of course, the lack of flexibility.
The "advanced mode" would basically be "here's a zone file, knock yourself out" - perhaps wrapped up in a pretty GUI to prevent basic syntax mistakes, but essentially raw access to records.
As compromises go the GoDaddy interface isn't too bad. It shows a page with a set of tables, each of which represents a type of record - it supports A, AAAA, CNAME, MX, TXT, SRV and NS records, which should be enough for all but the most advanced users. There are a few special links for specific tasks (for example, the TXT section has an "Add SPF record" link) which is somewhat like a "wizard" interface, but only has limited options.
In terms of PA offering a DNS management service, I'd say it has good potential to make life easy for users with simple requirements - offering a totally generic DNS service is quite a lot of UI work, though (although there are already plenty of providers making good business out of offering a very cut-down DNS interface). I think the "simple user" interface is probably the best fit with PAs currently offerings, as advanced users are hard to cater for and aren't going to find it tricky to set up CNAMEs and the like.
I agree it's not core functionality, but it might be a reasonable value-add for paid accounts which streamlines people use of the bread and butter PA services.
OTOH, it would mean dealing with BIND, which is never a pleasant prospect (unless you want to go with djbdns or something).
@giles: Belated Happy Birthday!