Good news!
To sum up, from the experience of Andrew1, kanishka and Scott_Holden the problem was caused by the presence of a SIM from T-Mobile (or MVNO thereof) in slot 1, and is fixed by moving the SIM to slot 2.
@palday @strongthany (who posted in the general update thread) @Fairphonemjm and @stern.ed : does this help for you people too?
Note: this might not be limited to T-Mobile SIMs so I would advise anyone who is experiencing the problem to swap SIM slots.