Hmm.. I'm assuming Your using PHP, I have something similar but use a Javascript randomizing rotator... and I just checked with a few tools and got confirmed that
I pass such a cloak test
Since PHP is server side, SE's will most likely *blindly believe* that the content appearing at the the occurring randomization *upon their spidering* of Your stuff... is static content.
That's why You'll fail a cloak test, and I don't - Javascript output usually never "happens" when SE's spider pages, since they don't execute them... and therefore the total byte length of my pages never changes in the "eyes" of the SE's.
Look into using JS instead if You don't want to switch from randomized rotation...
It also has a nice side-effect when You get swamped with traffic; less server side load... ;)
EDIT: another benefit; You can add something for the SE's to chew on in <noscript>SE-food...</noscript>