This definitely sound like a leaking vacuum servo. I have the same car as you and I had the same problem about three years ago. Each side of the floor vents is operated by its own vacuum servo however they are powered by one vacuum line so if one of the servos rubber has cracked and is leaking air both sides will not function... Simply take apart the center console (you are trying to get below and behind the radio) and the unit takes two minutes to replace... I picked up a used one from a wrecking yard and it has worked for the past three years. In the meantime you can jam some sort of object in the floor vent to hold it open and keep your feet from freezing. Good luck!

__________________
05 E55
03 E500