we have no ipsecN interface for either end of this connectionThe reason, it turns out, is that if the ipsec services were started before all the network interfaces came up, it is confused about which egress route to take. As I found on the Layer9 blog (and translated from German to English via Babelfish), it turns out you need to make sure that ipsec starts after the network has come up. The quick fix was just an IPSec restart:
sudo /etc/init.d/ipsec restart
And the long-term fix was definitely to just delay the ipsec a little. Add this to your /etc/rc.local file:
/etc/init.d/ipsec stopsleep 5/etc/init.d/ipsec start