Actually, cryptosystems that use cipher block chaining are more resistant to the "changing bytes / unchanging bytes" attack because the key will change depending on what data came first. If you're at least a little bit clever, you'll start with some information that's well-known but changing about the packet (such as a hash of the sequence number) in your encryption function, without actually including that data in the transmitted packet, and re-generate that same pre-seeding when decrypting.

If you do that, chances are good that you have to put a few bytes of framing (packet sequence number, or whatnot) that are un-encrypted up-front.