While it would not be a permanent solution my first thought to de-compact the substrate would to be to stratify it using an upflow. If you have a pump or power head you could hook a flexible line up to and stick something ridgid on the end (1/2" cpvc?). If the pump/power head had adequate power if you get a good flow under the subtrate by sticking the ridgid tube down into it it should stratify thus decompacting. You would want to repeat the process at various points throughout your tank until you are happy with the result. The reason I suggest this method is that it should pose less impact on your vegetation than completely removing it.
Regardless I wish you luck!
- Ian
EDIT: As an after thought I should mention that if you try this method it would be wise to preform a large (>50%) water change after as the bed is most likely quite 'dirty'. An alternative would be using a gravel vacuum (perhaps assisted by a pump) to stratify the gravel and remove the detritus embedded in the bed.