i would like to offer some suggestions :-
1, run this program if you can http://housecall.trendmicro.com/ it is free online to use, i use the paid for version and find it excellent

2, i also run hijackthis to try and find any browser hijacking program

3, if you can tell us what the software it is trying to sell you, there will probally be removeal instructions on the web

4, dont format if you dont have to