クライアント側(Mac)で、サーバー側が(Ubuntu)で生じた。
どうやらクライアントと、サーバー側の言語設定が日本語と英語で違っていたのでDid not find mosh server startup message が発生していたっぽい。
そこで Ubuntu側の言語を英語にしてみた。
/etc/default/locale
LANG="en_US.UTF-8"
これで解決した。
参考にしたのはこのページです。
https://github.com/keithw/mosh/issues/98