I agree, looks like he's drowning, rather than flying. I think the frantic leg movement is the culprit. Tried a head bob yet? HIs body is so static.
If you're testing the rustiness of your pixelling abilities, it doesn't seem to make sense to feature design, animation and pixel technique. I'd focus on one at a time, so that you could better focus on the area of need, but that's me I guess.