It  does sound like you have a cold running condition. I've just been there
and done that, and yes, if the coolant is not hot enough, it causes no end
of running problems.

It's easy  enough to replace the thermostat. Go underneath the car, look up
past the oil filter, and you will see a cover plate with a radiator hose
going to it. It has two 10mm bolts. Crimp all your radiator hoses with vice
grips or whatever and put a pan down to catch the runoff. Take the bolts out
using two 6" extensions on your socket. Pull that plate down, get the old
t-stat out, put the new one in, bolt 'er back on (with a new o-ring...) and
you're good to go. If your coolant is near new, strain it and pour it back
in. And don't forget to take off the clamps on your hoses! The whole thing
can be done in 15 minutes.

Still, though, look at the problem methodically. All the correct coolant
temp will do is enable your temp II sensor to give the correct reading to
the ECU, helping it to determine the correct fuel/air mixture. It has
nothing to do with the vacuum advance. You still need to set your timing
correctly.

Geza