Pues la única forma de saberlo es probándolo. Les sugeriría a los dueños de cibercafés instalar algún GNU/linux en 1 máquina y probar. Pero por supuesto: únicamente si lo saben administrar.
A mí sí me gustaría y creo que vale la pena, sobretodo porque es un ahorro para el dueño del local, además de facilitar la administración (de nuevo, solamente si se sabe hacer de antemano).
Obviamente no sirve para todos los casos: en lugares en donde la gente va a jugar no tiene sentido poner un GNU/Linux porque los juegos más nuevos no funcionan.
Office => openOffice o KOffice son más que suficientes para las tareas diarias, la mayoría de la gente no se dará cuenta
MSN => aMSN, aunque aún no soporta videoconferencia. Pero como bien dices se puede emular lo necesario. Aunque hacerlo con vmware sería tonto, ya que necesitarías de todas formas instalar un Windows...
"Muchos no van a entender"... muchos no entienden de windows tampoco. He trabajado en cibercafé y te lo puedo asegurar de primera mano. mientras resulte familiar, a nadie le importa si es windows, linux o Multics
Con este criterio incluso Mac, el "paladín" de la usabilidad y el diseño, sería complicado.
Saludos.