Check any firewalls and inspect some traces if you haven't. Never know what you'll find. We've seen tcp messages not properly reconstructing on some setups on just one port for some reason (not having anything to do with Kamailio). You could also try a non-standard port to see if it is any different. No reason it must be 5060/5061.
Might check out some of the tcp parameters as well.
This one in particular we are trying out disabled because with it on certain requests go out an ephemeral port that we don't have set up in our iptables. With it disabled it goes out a standard listening port we have setup and is preferred.
You should also set debug=3 for clues if you haven't. I suggest providing more detail if you don't figure it out. Could be so many different things.
Regards,
Ryan