Yes, if you've got rotating parts you also need to avoid passing too many cells in a time step too. I tend to aim for under 1 cell and go from there.
The DPM report means you may need more particle steps. Now, that could mean they're flying too far (time step issue) or that some are passing though a boundary/partition too often: ie both cause you to do a DPM calculation so use a calculation step. The former you're looking at with time step. For the latter check what the flow is doing and if you can try with half the number of cores and see what happens.