Thanks for all the suggestions - I tried the exposure range that Mike Ware suggested (2 - 4 minutes) but perhaps that is just not enough for my UV box. Typically, for Pt/Pd my exposure times are around 7 minutes.
FYI - the papers I tried were the following: Bergger 320, Strathmore 500 (new type), Cranes Platinotype, Cranes Kid Finish, Weston, and Bienfang 360.
The Strathmore clearly doesn't work due to a sizing on it - I encountered this with Pt/Pd as well. Most of the coating just washes away and the sizing won't clear either. I wonder if it will work with an oxalic acid soak prior to coating.
The Cranes Kid Finish and the Bienfang seem to work the best, but it's hard to tell without trying longer exposures. Only thing challenging with the Bienfang (it's actually tracing/drafting paper) is that it is so thin, it's like toilet paper when wet.
Obviously, I need to do some more experimentation with all of this and for now, I'm going to assume that I just need longer exposures. I may also try double coating as well. Ultimately, my goal is to try Cyanotype over Palladium.