Time Machine can't find Time Capsule - but can mount it
Turns out for some reason "Use dynamic global hostname" was checked under System Preferences > Sharing > Edit (computer name). Disabling this made everything a-ok.