Ok so I ended up just starting over, here's what I did.
Uninstalled XBMC from all boxen on my network...
Dumped and then dropped both xbmc_video and xbmc_music databases from my MySQL server, recreated the databases fresh and then configured my clients.
If you want more detailed information on step by step instructions on how to use a MySQL database as the backend DB let me know as there is a very specific step by step process that you have to follow or you will have problems.
Its working perfectly now, hopefully it will last.