"I believe the Common Travel Area is also a key issue as it commits us to open travel through the border which on the face of it seems incompatible with leaving the customs union."
No, this happens elsewhere already. Compare Norway - it is in a common travel area with the EU (Schengen), but out of the EU customs union. They're different issues.