Well I just tested it with my N-Card, and...It works perfactly. I just dropped it in and ran it with the default save type (auto in this case) and have played it and it saved properly. It ran fine on next bootup.
Its either the firmware I'm using or where I got the rom that is causing the running perfactly symptoms.
I think it has to do with the version of firmware I'm running. So I recommend upgrading your N-Card firmware to this:
http://www.qi168.net/forum/index.php?topic=108.0
Its called "Ultra N-Card", but it will run on any N-Card/clone. This firmware adds soft reset feature and a loading icon. So even if you don't play contra, upgrade to this firmware anyway. Go to the very last post on the above thread link for detailed instructions if your not familier with the firmware upgrade process. Otherwise just use the instructions provided on the first page.
Contra 4 should run without any fiddling around with settings or files, once this firmware is updated.
Don't worry this new firmware is fully compatible with any existing custom skin you might be using. Be sure to backup your games/saves and skins/global.ini files, before updating. Also, you want to turn off 3D Menu in global.ini file if you don't want the 3D interface since it will be the default option on a fresh upgrade. PM me or post at that forum if you need help with the firmware stuff.
Also note that the version numbers for above firmware won't be consistant with the version numbers of the standard firmware. The Ultra-N Card firmware though almost identical to the standard firmware, is more then likely a (better) software clone of the standard N-Card. I havn't had any issues with this firmware and so far seems to work better then the latest version of the standard firmware.
And last time I checked, I didn't have to change the save type for Zelda: Phantom Hourglass. It seems this firmware can properly detect its 4mbit save type. So I don't think you will have to change the save type to manual with that game either.
EDIT...
Well then after further playing. I didn't get the error when playing Contra, but now got that error when trying a different game....Oh well. Use the method already mentioned a few posts back. I still recommend upgrading to this firmware however. Its much better.