Ok, well as I mentioned the footfall noise is mainly due to noise transmitted through the structure.
So, therefore, you need to try and isolate the structure from the finished floor, and the finished ceiling.
Please realize that no matter what you do to the f/c assembly, not all the noise is going to go away. The type of noise that is especially problematic with this type of structure is the low frequency footfall noise, aka "elephant walk" noise, as the attenuation of such noise is more related to the mass and stiffness of the assembly than the thickness or the materials...Also, carpet+pad does an excellent job topside for reducing the mid-high frequency impact noise. You will notice a drastic difference in impact noise when you replace it with tile/hardwood. There are things you can do which you should consider when installing the tile/hardwood too...
Anyway...We'll concentrate on the ceiling since that is what you are currently working on.
I would recommend the use of resilient channels (RC) or sound isolation clips, in addition to sound insulating batts in the stud cavities. The general idea behind the RC's and clips is the same, 1) they help minimize (or eliminate) direct structural contact between finished ceiling and ceiling structure, therefore minimizing the structural noise transmission 2) they allow the ceiling to move slightly, which makes the floor/ceiling assembly and airspace act kinda like a diaphragm, which absorbs more airborne sound. Either one of these is rated to support 2 layers of 5/8" drywall. 2 layers is better than one, but not by a large amount, expecially for impact noise. If you have the means I would do 2.
In general, the clips do a better job, and they are easier to install, but they are a bit more expensive per sqft. Also, the RC's will only take up additional 1/2" of vertical space, while the clips will eat up about 1.5".
For the RC you'll want to use the 25 gauge Dietrich RC Deluxe. I'm not sure how easy these are to find for small scale installations, but, they are the only RC we recommend due to the
vast differences in performance among RC's:
http://www.dietrichindustries.com/products/pdf/52_53_DMF07.PDF
For the Clips, there are a few options out there now, but the most common is the PAC RSIC-1, made by Pac International.
http://www.pac-intl.com/pdf/RSIC_Advantage.pdf
Again, I'm not sure exactly how to locate these on a small scale. Best bet for either option is probably google, or by calling local manufacturer's reps to see if they will offer to sell you a small amount of channels or clips. These are primary used on large-scale multifamily buildings, since there is obviously no code within the same residence, and builders of single family homes typically do not go to large extents for sound isolation from floor to floor, or room to room.
The RC's install perpendicular to the joists at 24" o.c.. You attach the small, single leg to the wood framing, and then screw the drywall to the other 1-1/2" screw flange that is down 1/2". DO NOT screw through the flange and the joist!
The clips are screwed directly into the joists, and then you snap on a standard hat-track, which you would have to run every 48" o.c. perpendicular to joists. You then simply attach the GWB to the hat track. IIRC you should only have to use 1 clip every other joist, but check their site for exact details on installation. Here this should help
http://www.pac-intl.com/ppt/RSIC-1_Wood_Steel_Install.ppt#1
In either assembly it doesn't matter whether the insulation is in the top or middle or bottom of the cavity.
When you are installing either assembly, careful consideration must be given to the perimeter isolation of the ceiling, and any fixtures you install in the ceiling. You should cut the sheetrock 1/8"-1/4" short, and then fill in the gaps around the perimeter with non-hardening caulk. If you do crown molding, install it just under the ceiling and attache to the wall only. DO NOT rigidly attach it to the ceiling and the wall, as this will also short circuit the assembly.
Same goes for fans, lighting, etc...you can't rigidly connect stuff to the 'floating' ceiling and the ceiling structure without compromising some of the acoustics.
I hope this helps...If you have more questions or want info on the finished floor installation let me know and I will try to slap some more info together for you.