I am unable to start the MDS/Collaboration service, I suspect due to the the JavaRE being upgraded. However I have followed the instructions to change the path in the registry and restarted everything, but still having no luck.

This is described here: KB17872 - How to upgrade or update the Java Runtime Environment on the BES

I keep getting the following when I try to start the service: "error 1067 the process terminated unexpectedly"

Is there anything else it could be?

Should the BES be able to run on any version of Java or does it require a specific version - currently it's on the latest one?

BES installation will install latest verision of JAVA which packaged with BES installation files. Check which version of JAVA is installed on the server prior to installing the BES. Both JAVA version should be same.