How about trying this? Don't use any distro built on the 3.xx kernel. I think the Linux Mint 12 is built on the 3.xx kernel. Use one made from the 2.xx kernel. Go for something sure and stable like, say, Ubuntu 10.04.
I have faced some problems like that when I tried to install Linux distros on my old laptop. I do not know what is the real incompatibility issue between the 3.xx kernel and my old hardware but I have found, through trial and error, that distros built from the 2.xx kernel work fine.
If you want something that works fast, try Puppy Linux. I used the Slacko Puppy 5.3.3 without any problem. That's the latest distro from Puppy Linux and it has support for 3G modems, too. There is another new distro called Precise Puppy but it's built on the 3.xx kernel. I haven't tried it yet but I doubt if it would work with my old hardware.
If you still have problems, please ask and I will see what I can share from my own experience in installing Linux on my old laptop.