I filled in the gaps in the tilemap with a red color to see if it affects in any way the black artifacts on the screen.
Sure enough, the artifacts turned red, so this leads me to believe that the stripes we see on screen are because of a rounding error/precision on the Android platform.
If you look at the 480b screenshot you can see that the artifacts have a radial shape, which is even weirder.
I am wondering why the tests supplied with the Cocos2D-x work as expected. The most obvious idea is that the tests work because the 1px spacing between the tiles is transparent.
Anyway, this all leads me to believe that the code that slices out a piece of the tilemap is imprecise on the Android platform, although as far as I looked I could not find code that seemed to be specific for it with regard to tilemaps, which makes it even harder to debug/fix.
Hope this helps anyone who is daring enough to try tackle the problem