Cannot add witness on sql 2005

I'm trying to set up a witness for database mirroring. The two mirror
partners set up without problems.

2 installations of Sql 2005 std
1 sql 2005 express (witness)
using DNS name resolution

All are sp2 9.0.3042 (so the issue described in KB article 930283 should not
apply)

when I try to use the wizard to set up mirroring with a witness, following
MS instructions I get

the alter database command could not be sent to the remote server instance
'tcp://****' The database mirroring configuration was not changed. Verify
that the server is connected and try again. (Microsoft sQL server, error 1456)

The instances are on three separate machines. All can see one another, and I
can open all three instances from server managment studio.

the primary database is loaded, the mirror is loaded with no recovery. I can
successfully mirror them without a witness, the problem occurs when I try to
mirror with a witness


Further details:

I am using th wizard: tasks\mirroriing\'configure security'\

I select the three components using the wizard (primary, mirror, witness)
This is the summary provided by the wizard:

On the principal server instance, na-flo-sql-01
Modify the following properties of the mirroring endpoint:
Name: Mirroring
Listener Port: 5022
Encryption: Yes
Role: Partner
On the mirror server instance, NA-FLO-SQL-02
Modify the following properties of the mirroring endpoint:
Name: Mirroring
Listener Port: 5022
Encryption: Yes
Role: Partner
On the witness server instance, NA-FLO-DPX-01\SQLEXPRESS
Modify the following properties of the mirroring endpoint:
Name: Mirroring
Listener Port: 5022
Encryption: Yes
Role: Witness


after a while the Database Mirroring Security wizard reports as follows:

Configuring Endpoints

- Configuring endpoint on principal server(na-flo-sql-01) (Success)

- Configuring endpoint on mirror server(NA-FLO-SQL-02) (Success)

- Configuring endpoint on witness server(NA-FLO-DPX-01\SQLEXPRESS) (Success)

But after all that reported success, when I click 'start mirroring' I get
the error discribed in the beginning.