Hmmmm, that's interesting. I didn't realize it until now, but I guess I've never had to move a layer -- I've always just created them in place.
Now this will all be conjecture on my part since I've never tried it, but it's probably worth a try!
Layers are essentially just specially-marked groups. Granted, they have some kind of 'layer data' associated with them (the AILayerHandle would be proof enough of that, since it's not the same as the AIArtHandle that represents its group art). Since the layer information isn't really changing, and the layer group art is really how a layer is tracked in the file, I'd suggest moving that guy and seeing if it works. To that end, use AIArtSuite::GetFirstArtOfLayer() and then try AIArtSuite::ReorderArt(). This might be completely wrong, but if I was going to do it, that's how I'd try it first. I mean, it's got to be possible; 95% of Illustrator is written in its own SDK, so I imagine the Layers palette has to manage it somehow!
As for symbols, I've never encountered any restrictions that I can tell. We routinely create new layers and dump a ton of symbols on to them, and as far as I can tell we're using kPlaceInsideOnTop! And the layers are even sorted, so they can be literally anywhere in the hierarchy.