Mirroring - totally stumped, need some help.

Alright, I've been at this for some time now and I am now officially completely stumped.
This is the error that I have been consistantly getting and cannot seem to resolve:
The server network address "tcp://<servername>:5022" can not be reached or does not exist. Check the network address name and reissue the command.
(Obvioulsly '<servername>' is replaced with the real name)

I just dont get it. I've tried everything I can think of.
Incoming/Outgoing TCP connections enabled? YES
T1400 flag? YES
Tried using strictly t-sql to set up mirroring? YES
Made exceptions with firewall? YES
Tried Telnet on port 5022? YES
Tried manually configuring certificates? YES
... you name it, I've probably tried it. I just cant seem to get past this and would REALLY appreciate any help any of you can provide.
BTW: this is on vers. 9.00.1399.00 (Developer...both machines).
Sorry if I am vauge on any of the details, just ask and I can provide any info you need.

Fire up profiler and turn on the Broker:Connection (no, not a typo) category of events on both machines.

|||Alright, tried that (thanks Michael) ... but still nothing. Here is what I'm doing:
1-Open Profiler, create new traces for the principal and mirror machine and run them (Broker:Connection).
2-Go into SQL Server Management Studio and attempt to start mirroring.
This results in the same error as before and nothing is being picked up in the trace, am I not doing something right?|||Alright, I'm pretty sure this is some sort of problem with logins...
In the error log I'm getting this:
2005-12-06 11:51:33.81 Logon Error: 18456, Severity: 14, State: 8.
2005-12-06 11:51:33.81 Logon Login failed for user 'sa'. [CLIENT: xxx.xxx.x.xxx]
This might make some sense if I was using SQL Server Authentication...but I'm not, I'm using Windows Authentication...so why would it even try to use 'sa'?
|||You mention:

(Obvioulsly '<servername>' is replaced with the real name)

Just want to make sure you have used the fully qualified name, i.e., server name and the domain name.|||You mention:
Tried using strictly t-sql to set up mirroring? YES

Can you list the exact steps you followed, including the T-SQL statements you executed and the result / error you got on each one.