Just so everyone knows I have found out what the issue is.
As part of the 3.5 console installation, the program tries to set the server service to automatic. Since our network people disable this using GPOs the install program could not do this. Instead of telling me that was happenning, it just said that the server service was not running.
As soon as I took the machine out of the domain, bypassing the GPO, I was able to start the server service and install the console.
McAfee has acknowledged this issue and is supposed to write something up regarding it. They also told me that the server service is not needed for the console. It is only required for MSDE installation, which consoles do not need anyway, hehe.
This issue has been fixed for ePo 3.6 already.