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
2010-05-20 13:02:56