I recently had this problem on an AWS EC2 instance. As I was just deploying services there I really wanted mosh to work and spent some time debugging the problem. Including using tcpdump and netcat to verify that traffic can indeed pass.
I had everything in place in the AWS security group and allowed incoming UDP traffic on ports 60000-60010. So why was there still a problem? A first clue was some output I had overlooked earlier
/usr/bin/mosh: Using remote IP address 192.0.2.204 from $SSH_CONNECTION for hostname firstname.lastname@example.org
It turns out that mosh can use different mechanisms to determine which address to use as remote IP, and this case it was using the wrong one. This problem can be fixed with a command line argument, see man mosh:
In my case the remote IP should be whatever the local host thinks it is.