First off, great scores! Secondly, the first thing that jumped in my head was when you said she is coming home in tears and is asking for private schooling.... My Mom intuition may be off here, but is is possible that you have 2 issues going on? One being bored in school, but possibly, 2 being some other school related issue with friends or what not that you are not aware of? If this is the first time you are seeing her "act out" about school, perhaps the boredom is in addition to another issue that maybe you want to see if that's a possibility at all? I just instantly thought that requesting to switch schools for a child that age (when many can be so close to their friends that they wouldn't dare think of switching) might signal that boredom isn't the only issue. Perhaps if you find out it's something else, by resolving that issue too, you can save the cost of tuition while treating the issue of boredom at the current school as well?! Again, I may be off totally without knowing her but it was the first thing I thought of.
I would start with finding out what the real issue is, then if it is truely just boredom from lack of challenge, come up with a plan to approach the school. It helps to have suggestions as they have already tried math packets etc. I hope I am wrong and it's just lack of challenge, but that's no easy feat in and of itself!
Good for you for being on top of your child's needs though!