I'm trying to peer over a tunnel, but I can't get out of the Connect state

This normally happens because BGP sets the ttl to 1 by default, and your tunnel is inheriting the raw path TTL. Set the TTL on your tunnel device explicitally (how to do this will depend entirely on the tunnel device you are using, so check its documentation for more details)

Another solution is to enable ebgp-multihop on both BGP speakers, but I'm not sure this is a 'good' solution. Setting the TTL seems like the right thing to do here.

TTL Settings for BGP peering in debian (route2)

To get my BGP link to run over an IPv6 tunnel I've had to set the TTL of the tunnel to 255 by adding 'TTL 255' to the tunnels stanza in /etc/network/interfaces. If setting the 'ttl 255' fragment to your tunnel stanza doesn't work, try adding the following

up /sbin/ip tunnel change $dev ttl 255

Where $dev is your device name.

So far its working for one of my tunnels, just have to wait and see if it works for the other