Hmmm, managed to get hold of a compatible card reader. Reformatted the card via the card reader, using quick format. The card correctly reported 4Gb capacity. Connected up the GP2X via USB, and verified that 4Gb was indeed available.
Reformatted the card using my old reader, and the capacity...