I just checked the IMAP server mentioned above…
openssl s_client -tls1_2 -connect host59.servers.prgn.misp.co.uk:993 - works 
openssl s_client -tls1 -connect host59.servers.prgn.misp.co.uk:993 Handshake failure 
So this is indeed a TLS problem and your provider has coincidentally turned off TLS 1.0 when you were traveling on 1 July. This is not surprising, as it is required to turn off TLS 1.0 from 1 July on to be PCI DSS compliant. Moving to a different mail provider that still supports TLS 1.0 probably won’t help you for long, as they will move to TLS 1.2+ sooner or later.
One thing we haven’t mentioned yet: K-9 Mail only supports TLS 1.2 from Android 4.4 on. As you’re still using Android 4.2.2, K-9 Mail can’t do much. There is an alpha version of Android 4.4 provided by Fairphone here, it will solve this particular problem, but might bring new problems.