http://shadowcat.pcplayground.com is a PHP Nuke site
Up until a few days ago was sending the new user registration emails with no problem, but now suddenly it has stopped, I really have no idea what it could be though! And I am pretty sure I have not touched the database in any way that would affect that

Have you tried sending it to multiple email addresses? If not, it may one of the servers in between this server and your email server that could be damaged.

Have you checked your spam settings? A lot of spam programs will block php-nuke emails.