It seems that something has broken with WordPress 3.4.1 as none of my contact forms are working now they all show the 404 "not found" error. I double checked that all the short-code syntax was correct as per the FAQ and this did nothing as all of them were correct. I got all of them working fine and haven't touched them and noticed since I updated WordPress to 3.4.1 that none of them show up. I did also make sure Contact form 7 was up to date at version 3.2 after seeing this problem. I need to find a fix to this as soon as possible or I will have to find another plugin. I have used Contact Form 7 for quite some time and have never had any problems until now.
Also please note that no other plugins have been installed since this was last working and I'm not going to deactivate all other plugins and revert to the default theme as this is on a live church website and I don't want any further interruptions to the site than there already are.