Well, I couldn't hold back after my redesign and leave the sidebar navigation the way it was, so I pulled an all-nighter (ok it was just a few hours) and updated the entire left sidebar (navigation, search, random quote...).
The update was not as simple as it seems since the other parts of the site still use the old design and since I didn't want to duplicate any code I had to resort to some PHP tricks.
Eventually I got it working the way I want (for now at least :) so I can go to sleep in peace...