We did get to the bottom of it eventually. Part of the problem was that we did not realize (because it was not documented anywhere) that the "Invalid Profile" message iOS devices were receiving was not some weird bug, but the result of the mdps-max-devices attribute being applied. Apparently due to the constraints of the iOS over-the-air provisioning method, ClearPass could not return a sane error message indicating that a user had already onboarded their maximum allowed devices. Instead, it just sends out a bogus provisioning profile and leaves the user scratching their head as to why things went wrong.
This problem was combined with the other issue that we ran into which is that ClearPass was treating usernames as case sensitive during the onboard authorization process. This resulted in users being able to exceed the max devices limit by changing the case of any letters in their user names (e.g. - tom, Tom, and toM were all being treated as different users). iOS has a tendency to capitalize the first letter of usernames...
I am glad to say that these issues have been (mostly) resolved in the 6.1.2 patch release. There is now a check box to disregard case-sensitivity in usernames and now an explanatory error message is displayed after the "invalid profile" message during iOS onboarding if users are smart enough to switch back to the web browser to see it.
Anyway, thanks for the assistance in this everyone!