Encrypting or obfuscating transport stream identifiers in SSL-like connections
Use a variation on your shared secret-key encryption proposal: Every packet has an encrypted header for which the plaintext is the connection ID concatenated with the packet sequence number. After successfully receiving a (connection, n) packet, the next packet received on that connection will be (connection, n+1). Store the encryption of (connection, n+1) in a hash table and remove the expired entry for (connection, n). When receiving a packet, do a hash table lookup using the packet's encrypted header word to find out its associated connection. Obviously for this to work, sender and receiver must use synchronized ciphers (e.g. a stream cipher initialized with a negotiated IV and the shared secret key).

You can easily extend this algorithm to deal with longer sliding windows by adding hash table entries for sequence numbers n through n+k. The space cost is O(mk) where m is the number of open connections and k is the length of the sliding window.