I think my sister's computer was infected with a similar thing such as this the other week. It didn't seem to slow down her computer much but her homepage was hijacked, search page hijacked and toolbars added to Internet Explorer. I managed to remove most traces of it the other day but it took a good 2 hours and I still haven't managed to reclaim the search page.
A format would be ideal but I don't think she would be too impressed (me neither because I would have to sort out her mess!).