I imagine you'd also have a hard time getting collision detection and such working for two playable characters.
That's true. From what experiance I have with SMB, I'd say you'd have to rewrite large portions of the game engine to get it to work. I wouldn't say it'd be impossible, but you'd have to know ASM and the NES well enough to basically write your own games to be able to pull it off.