Just out of curiosity, what sort of firewall do you have? I use McAffee. Apparently I can open specific ports (and I tried explicitly opening port 23842 or whatever it was, though I have absolutely no idea if I did it correctly) and it also says that by setting the security settings to "standard" it will allow all UDP communication. Doing this still doesn't fix the problem, so I'm really starting to wonder what's up with it or if the root of the issue lies elsewhere.
On a different note, it's interesting that we're thinking alike.
I'll try out the levels you listed as well.
Edit: I've played through a couple of levels so far, and although I thought "ariel" was a highly interesting/amusing/generally cool level, I don't think it would work well for multiplayer. Namely because the level is basically a 3D star and if you shoot weapons inside of it then it blows up quite badly. Kaboom.
"Hunting halls" was another one and it seems quite nice. Should work well with multi.