A: 

Is this problem being caused because I'm invoking updateMapOverlay from inside a non-UI thread

Yes.

I'm also calling updateMapOverlay() inside another Thread (a TimerTask) that is invoked on regular intervals.

Why are you removing and adding an overlay constantly? Just update the overlay and invalidate. See here for an example of updating an overlay asynchronously.

CommonsWare
A: 
Soumya Simanta