I think Daniel Lichtblau gave a useful answer in his comment. This is to get it on record.

They (the present example and the Solve one) are similar issues. At heart, as noted by @Rojo, it has to do with internal ordering having an impact on simplification, cylindrical decomposition, and other under-the-hood functionality that is called upon by the likes of Integrate and Solve. We'll look into these examples but I am doubtful as to whether they are readily remediated