At highend, there is a script that was just released this weekend that MIGHT help you....

Do a search for: "Instancer Random Rotation v0.0"
Or on thier main maya page, it;s the 4th or 5th link down on the new scripts page...


Also K has a good point too, but I also am not in front of Maya at the moment...