Wow, karandpr and 9to5cynic, glad you're available to help. But seriously, it's absurd that a new Mint user should need to be editing config files and executing command line programs to recover a package manager database. Defeats the whole point of a distribution designed for newbies!
If this gets too hairy, suggest you just install over it again. The nice thing about a live DVD distribution is that you can totally hose it and all you need to do is reboot and you're golden again. It's a good way to debug risky operations that would be hard to back out of with a full install.
Veni, Vidi, Droidi!