Thank you Tim,
I upgraded, thought Ubuntu would have chosen latest.

GRAMPS: 3.4.2-1
Python: 2.7.3 (default, Aug  1 2012, 05:16:07) [...
BSDDB: 5.1.2 (5, 1, 25)
LANG: en_US.UTF-8
OS: Linux
Distribution: 3.2.0-37-generic-pae

I still get 362 people.
Even after I wrote a little script to pad extra zeros in the less than "%04d" ID's
True I no longer have the ~/.gramps directory from my old computer.

What I did is made a sorted list of all the ID's, and iterated through it. For each ID that was not in the "%04d" format I opened the gedcom file and replaced every instance with the next highest "%04d" formatted number.
 I now am back to 443 individuals :)
Thanks for all the help,
Ben