Finally got it to work. Since I'm using a Galaxy Mini 2 (S6500D) I used the service menu code *#*#1575#*#* and set the following things:

UP MOLR STATE: Set UP MOLR STATE
3G MOLR request type: Set LocEstimate type
TLS SESSION: OFF

It works now, although i have to turn on location services and manually start and stop sessions each time.