Do you have some reason to believe that Google seriously hosed the Java implementation on Android or these guys have massively increased the efficiency of the Python implementation? Otherwise, it seems the answer would have to be yes.. the same algorithm will usually perform (much) worse in Python than in Java.
Note I don't mean to slam Python here.. just being practical. Python's my primary language. Development efficiency usually trumps execution inefficiency.
Python is going to chug even on relatively simple action games. I did write some 2D stuff in Pygame/SDL and Pygame/OpenGL back in the early-mid 2000s that could do 30FPS, but to do it was akin to writing in BASIC on an 8-bit; you had to micro-optimize in a fairly brutal way, one which obscured Python's powers. Things like rendering a tilemap could get huge speed boosts simply by avoiding nested loops in favor of a cache. Even using OpenGL wasn't really enough to secure a comfortable margin of performance.
If I did it again I would have an easier time because I missed a few critical constructs back then(most notably, the array package). It still wouldn't be pretty, especially not on a phone.
