Hi Steve,
I've set the SQL Server on the witness to run as the local sysadmin account just for testing purposes. The windows sysadmin is also the sysadmin for the database, so there should be no permission issues. However, the problem stayed exactly the same, so it does not seem to be related to this.
Regarding the questions in your second post: Yes, I have several times tried to telnet into the principal and mirror servers from the witness. I also tried telnetting into the witness from the principal and mirror. All of this worked, thought the connection is quickly closed again by the host. That seems normal though, given that it is probably expecting me to provide a certificate and I am just idling.