Che io sappia non si può modificare direttamente una chiave di un hash. Quindi suggerisco di fare così:

%hash # hash che contiene i numeri fax
$chiave_da_cambiare = '123 456';
$chiave_nuova = '123456';

$hash{$chiave_nuova} = $hash{$chiave_da_cambiare}; # assegni il valore da salvare alla nuova chiave

delete $hash{$chiave_da_cambiare}; # cancelli la vecchia