I want to get my coordinates every minute, even if a user is not moving. So i used requestLocationUpdates with the following parameters:

  locMgr.requestLocationUpdates(
                    LocationManager.GPS_PROVIDER,
                    60000,      // minTime in ms
                    0,      // minDistance in meters
                    PosljiLokacijo.this);

But when i test it on my HTC Hero (2.1 Android) and i am not moving, onLocationChanged() is never called. If i change minDistance to 1, then i get a few updates at start but after that, they come in very unregular intervals.

How should i choose these 2 parameters (minTime and minDistance) to receive coordinates every minute?

I don't think "minTime" or "minDistance" will help in this case, unless: save the last location into variables and output them every minute. Let the locationManager overwrite those variables so after a minute, the location change becomes visible. That way there's no need to wait for an update as your variables always hold the actual position.

You can also retrieve the location from the locationManager and request the location again after one minute (or whatever you'd like your interval to be) without using requestLocationUpdates.

e.g. take a look at the Timer to set a repeated call to your method that gets the location: http://developer.android.com/reference/java/util/Timer.html

That way you should also save battery as the system won't be looking for updates all the time.