Are you sure your camera supports 4GB cards?
There is a limit on
FAT16 file systems with 32KB clusters of 2GB. If the camera supports 64KB clusters (unknown) or uses FAT32 (supported), then you are in business. If you formatted it in the PC with FAT16 and 64KB clusters then you might have an issue.
Always pays to RTFM...