Penso que o principal problema está no design.
Algumas sugestões:
- Utilizar outro tipo de letra - Arial ou Verdana por exemplo
- Substituir os menus do lado direito por texto - as imagens são más para os motores de pesquisa
- Utilizar outras cores - acho que está muito vermelho
- Colocar a pesquisa no lado direito - ninguém vai até ao fim da página para procurar a pesquisa