Now the real question is why they didn't go with a Popeye game. I've heard two reasons -
1) Supposed rights issues according to David Shef's Game Over book, but that seems a little odd considering they did make a Popeye game for real the following year.
2) Unable to properly render the Popeye characters given the technology they had available. This seems a little more likely given what was put into Mario's design to make up for the lack of versatility in the graphics display. It's also been noted that the actual Popeye game they made used a technique that devotes less detail to the backgrounds in order to make the characters' sprites look better.
Or maybe it was a combination of both?