I figured it out! Transform Each doesn't work on sub-layers. The objects must be on a layer at the top level of the document.
That's the magic trick? I'll give it a shot tomorrow!
In the meantime I managed to convert 3,424 arc symbols into 3pt circles using the Convert to Shape and Expand Appearance functions. I was pretty amazed that Illustrator didn't even blink and only took a couple seconds to process the whole batch. Did Adobe get rid of the Find and Replace Symbol function? I know Illustrator used to have something... (I've had a year of Freehand and am catching up with CS2)... where did it go?