"Então basta mostrar um grafo que apresente um resultado errado ?"
Sim.
"qual o problema de permitir pesos negativos nos problemas de encontrar um caminho mínimo simples ?"
Com pesos negativos, algumas propriedades básicas deixam de valer. Por exemplo, não é mais verdade que segmentos iniciais de caminhos simples mínimos são caminhos mínimos.