Or (I haven't tried this.. but) you could add "phpmyadmin.domain." to point to "phpmyadmin.<hostname of your server>." in the dns template, and then make a global phpmyadmin directory somewhere on your server, add the "phpmyadmin.<hostname of your server>" subdomain to point to that directory.
Use cookie/session auth on phpmyadmin. Now anyone that goes to phpmyadmin.theirdomain.com should get to that installation of phpmyadmin. They then enter their own credentials and it will bring up their own databases, and look like its a personalised version.
I say again, I haven't tried this but it should be doable. Especially with the new auto base URL detection that the new phpmyadmin's use.
Think I'll try this when i get back from work.