Heh... I found out 123D will and does boolean them. I was selecting the parent of the paw instead of the individual blocks in the browser... Apparently it's something they are fixing. Anyway, if I select each solid piece of the paw it booleans fine. The problem however still lies with exporting to *.stp where virtually every program broke it back into individual blocks that need to be booleaned again... I've learned my lesson with pdfs.