GATT connection timeout?

Ahh. Got it:

If any of the discovered characteristics have 128-bit UUIDs which are not present in the table provided to ble_vs_uuids_assign, a UUID structure with type BLE_UUID_TYPE_UNKNOWN will be received in the corresponding event.

So that's the issue by the look of it - a full 128 bit UUID for the service. However if you search for the service by the full UUID, I'd have thought it would find it.