Apparently, I'm not the only one, who does not exactly like the new Start menu. There is already a tool to get Windows 7 style Start menu back.
If you're not a fan of Live Tiles then this might be the Start menu you're looking for. It's literally identical to Windows 7, complete with the search interface and all programs view.