Alright I figured out what the problem was, and I feel a bit stupid about it to be sure 
In Android I am dynamically loading the assets from an external swf to be able to update any time from my remote server (other than on iOS where I use swc). The gfx swf has about 150 frames on the timeline with all the different assets (for access convenience in Flash CS). Now when I load the swf, I never put it on the stage, I just access the necessary classes through getDefinitionByName(). But what I was not aware of was that the loaded swf will loop all the 150 frames the whole time in the background. So every few frames, a bunch of MovieClips where destroyed and new ones created. And this had a notable impact on the performance on Android.
By just stopping the swf on the first empty frame, I was able to increase the performance to around 40 FPS vs 50 FPS on the iPhone 3GS. Taking into account the higher display resolution for the Samsung, I would think this is reasonable.
I have to say during the process of debugging, both FlashDevelop profiler and Adobe Scout for Android where of great help. And I learned myself yet another huge lesson in ActionScript 
Thanks