Are you trying to format a Compact Flash? I never had any problems with CF's, but some problems with SD cards.. I don't think there is a problem if you are using a compact flash adapter, unless there is physical damage. Could the CF be corrupt from formatted on the PC? Did the CF adapter work before?

If you are not using compact flash....get the CF and adapter, they are stable and 4 gigs is more than you can use.