Blastman: in ACDC 2. Use Oil Body, and you'll run into him every time there!
Diveman: Seaside 1. Use Fish, and sneak run.
Circusman: ACDC 3. It's not a big area.
Judgeman: Green area 3(im pretty sure).
Elementman: Sky area 1(the same area of that cafe)
Colonel: Underground 2(If you're going after Bass BX here, be careful of Colonel SP).