The upgrade is something that is possible, however it requires opening the unit and installing a logic board with a larger amount of memory in it. Of course, by doing this, you would void your warranty on the device. The sizes available are the same sizes that Apple offer (8GB, 16GB for $189, $239, respectively). Rapid Repair out of Michigan should have some in stock, but you will need to call them to see what sizes they have in stock.
Are you having trouble with the ipod flash memory? Please see http://www.ipod-repair-guide.com for information.
