Wayne-
This might be of use to you:
http://www.cisco.com/univercd/cc/td/doc/product/software/ios122/122cgcr/fqos_c/fqcprt4/index.htm
Gets pretty technical pretty fast, but you should be able to do what you need to using Class-Based shaping.
Of course, the exact implementation depends on the answers to Mikesters' questions, but this is usually how Cisco pulls this off.
Personally, I'd get a professional Cisco guy in to do this... it's REALLY easy to mess up if you don't know what you're doing, and some of the subtleties can be tricky to get right if you're not familiar with the configs. Shouldn't take him/her more than an hour or so to figure out what you have, figure out what you need, config it, then test it, and it should be doable "hot" or "live", without requiring any real downtime.
$0.02