I've updated my free Twisty Puzzles for Android Phones and checked them on HTC Desire.
I've added the Overlapping Cube. YouTube
I have also reissued the existing FTO and Megaminx, which were originally written for G1 and had a few niggles.
They are for Android 1.6 and later and can be downloaded direct fromhttp://msscoventry.freehostia.com/Mobile/games.html
I am also intending to transfer Cuboids
and Backspin from the iPhone to Android.