FAT32 is only supported by Windows 95 version B (OSR2, OSR2.1) or version C (OSR2.5).
It is not supported by the original version, or version A (OSR1). To check, simply right click on My Computer and select Properties. The dialog displayed will tell you what version you have.
Win95B and Win95C both have a conversion utility for FAT32. Normally this is found under Programs | Accessories | System Tools....called Drive Converter (FAT32). Simply run this program. It does not require you to reformat and re-FDISK.
If you cannot find it in the Start Menu, have a look in the Windows directory for CVT1.EXE, or check that it has been installed under Windows Setup in the Add/Remove Programs in Control Panel.