I tried it with a few T-Mobile SIM cards, all of then work fine on other Lumia devices (same location, same SIM, different device).
Tried resetting the phone and flashing it back to 8.0, still won't connect.
Is there anything else I can do other than sending it to Nokia?