I also use PicStart and you're right it doesn't support all the USB PICs. I asked to Microchip about that. They told me they didn't have any project to implement USB PIC in PICSTART. A bit stupid in my opinion but...

ICD2 seems to be the one to use now. I don't have it but heard good comments on.

I use BK Preecision 844A. That one support most PIC and ALL usb PICs + a load of other EEPROM and MCU.