It seems like Michael was right - and although Windows 'supports Teredo out of the box' whoever is on the other end of that tunnel doesn't support Microsoft.
After signing up for a tunnel with HE, and running their configuration commands, it worked instantly and Remote Assistance Easy Connect was also able to connect.