Using certain VC++ 2005 (maybe 2008) merge modules have been seen to make uninstalls slow. Otherwise, system restore might have something to do with it. You might have an uninstall custom action that's slow.
Doing a command line msiexec /x {your productcode guid} /l*v <path to a text file> will create a log containing times, so you may see some times that indicate where it's slow.
Phil Wilson