This may be fairly random, but I think you and I are working on the same project I've been doing the Kinect graphics for the 360 on a strikingly similar background ;)
The approach I used to get fairly good results was to just do a simple downsample to a half size target, leveraging bi-linear filtering. If you need to maintain the size of your normal map as you have it now, this may not work, since it thins out the appendages, but to our 120x90 image it looks great. I also had some really great results by applying a gaussian blur on top of everything.
Hahaha I see , good luck with your 360 project. mine uses Unity
i did a little bit tweak on my bilateral filter and it looks better right now. yes you are right by downsampling and applying gaussian filter, the result is more consistent and less noise, right now i choose not to lose the detail and keep on 320x240 resolution instead. I got depth map and normal map, hey i can add SSAO effect now