OK, I have some captures finally.
They are in LibPCap format and were generated by Wireshark (the project formerly known as Ethereal) so should be viewable by just about anyone.There are four .pcap files in a single .zip.
192.168.42.x is my internal range here. .1 is the pfsense box. .254 is a Linksys WRT54G running Sveasoft Talisman (which has working UPnP support). .2 is my Windows 2003 server - it does DHCP and DNS for the network, and it is what I was capturing from as well.
xbox360-startup.pcap is the dump from the bootup while connected to the pfsense box. Not much interesting here - you'll see the SSDP packets where it just checks for the router, and then a bunch of UDP as it connects to XBox Live.
xbox360-test_live_connection.pcap is the results of the "test my connection to Live" from the Xbox, while still routed through the pfsense box. You'll see a bunch of SSDP queries but then nothing else other than the UDP traffic once it signs in to Live.
xbox360-startup-linksys.pcap - the name is obvious. SAme as the first, but with the default route of .254 and the pfsense box off the LAN. The Linksys does UPnP. Since the Xbox doesn't yet need a hole punched in the firewall, it doesn't try to do any more with UPnP other than check for the router.
xbox360-test_linksys_works.pcap - this is the money shot. You can see that there's a brief SSDP exchange over multicasting, and then there's a unicast exchange, and then the 360 and the Linksys start a TCP conversation. It's not on port 80 so Wireshark doesn't decode it all pretty, but if you look at the data it's just SOAP/XML/HTTP exchange. I'm guessing that this is where it actually does the magic of opening the port in the firewall. If you can mimic the Linksys's responses here it should work.
Hmm. I think I might know what the problem is. The Location: line that miniupnpd spits back is "http://<firewall ip>:1900/rootDesc.xml" Note the uppercase D in "rootDesc.xml". $5 says that the 360 does an lcase() on the URL and tries to hit it like that...? Although I don't see any such attempt and 404 - it never appears to even try a TCP connection with the PFSense box (or at least there's no packets showing this, and I logged *). The source for Sveasoft is open and we could port over their work, but it's probably GPL vs BSD license and I know that is frowned upon.
I don't know the slightest bit about BSD developent or else I'd try to lend a hand. I've had some courses in C/C++ so I might be at least remotely helpful, but I don't have a clue about how to actually work on a real project (about all I've done is 2-3 source file jobs, with a header or two and maybe one library involved).