I would compare those results to results from similar tests on the 8GB card.
If the 8GB card looks OK to fdisk & Gparted then I would be inclined (after backing up any data I wanted to keep) to wipe the 16GB card properly and rebuild the MBR/partition table and recreate the partition and format it.
If you are doing this it might be best to write zeros to the first MB or two of the card to ensure it is properly cleaned.
Thanks, I just did all that, and was typing this below as you posted; The only thing I haven't done is write zeros to the 4MB boot sector (if that's what it is), how do I do that? :
Okay,
I redid everything with GParted, deleted, new partition FAT32, shrank the size to exactly the same as my Samsung 8GB card, set all flags the same, same Label.
It still doesn't mount and GParted says read errors when it's in the camera (as a removable drive of course), force GParted to read it and it says all unallocated.
The card then works perfectly in the camera, files readable when in the normal card reader.
Works in my Android tablet too

I'll try the camera forum, ask if anyone has used a Lexar 16GB card, but I don't think they'll be much help as it only has this problem under Linux as far as I can tell.
Weird
