I had a similar problem with a 4 gig CF in my A1200. I had first tried a borrowed 512 meg unit and it formatted to full capacity with HDToolBox. Then later when I had the 4 gig unit I tried again but only got 512 mb.
I then made a a new copy of my original 3.1 install disk and got 4 gigs without any problem.
Was something being carried over from the installation of the smaller card?
