Ok, I've tracked down the cause of this problem in the Debian kernels:
they are disabling CONFIG_SECURITY_NETWORK, which disables all of the
LSM socket hooks. Thus, SELinux never gets a chance to classify the
socket inodes as socket objects via its selinux_socket_* hook functions,
and SELinux can no longer distinguish them from sock files at
d_instantiate time because of the removal of the i_sock field in 2.6.12
(which we didn't view as a problem at the time because we had the socket
hooks to address the issue).
I'd suggest asking the Debian kernel maintainers to entertain the notion
of enabling CONFIG_SECURITY_NETWORK. If they are being driven by
performance considerations (and have actual data to show that the mere
presence of the LSM hooks is having real impact, even with selinux=0),
then possibly CONFIG_SECURITY_NETWORK could be tightened up to only
apply to the hooks that are on the critical path (e.g. sock_rcv_skb is
likely the largest concern).