Suele considerarse más acertado colocar el menú de navegación o contenidos a la izquierda o arriba en la parte superior en parte porque es lo más habitual -o venía siendo lo más habitual hasta ahora. En general la columna o parte derecha de la página suele ignorarse cuando su presencia es habitual porque se relaciona con contenido adicional y sobre todo con publicidad.

La columna con menú de navegación también es contenido y además en ocasiones contenido vital para que la gente de un vistazo pueda saber dónde está y si le puede interesar el sitio más allá del contenido principal puntual -esto es especialmente útil cuando se llega de rebote a un sitio web, lo que es muy habitual.

En cualquier caso esté donde esté la columna también debe contener lo mínimo imprescindible para no saturar y resulta de utilidad -como bien dices se ven columnas por ahí totalmente ilegibles excepto para el que la hizo y sabe de antemano qué contiene y dónde, pero eso no cuenta a favor ;-)

¡Suerte con el rediseño!