I think it has something to do with the fact that every big tile is 4 smaller ones. If you zoom in enough you can often move your Sov so that he's in the right tile again.

Yup, same issue here... Here is a screenie (my chap is to the top right of the blue selected square). It seems to do this after I die and respawn. Loading a save from this point fixes it.

System specs if it helps: Athlon x2 4200, 4Gb RAM, Vista 64, ATi 4650 latest drivers. All patched etc.

yeah, thats exaclty it like on the screenshot - happens quite often here

It happens a bit to me (Cloth Map or otherwise) usually after the unit in question is killed or moves within the borders of a City.  Happens to the Sov more so than Champions.