See the BUGS section of the MLDBM docs. You need to extract the whole array into a temporary variable and push onto that, then assign an array reference to the result back to the tied hash.

From the MLDBM pod:

Adding or altering substructures to a hash value is not entirely transparent in current perl. If you want to store a reference or modify an existing reference value in the DBM, it must first be retrieved and stored in a temporary variable for further modifications. In particular, something like this will NOT work properly:         $mldb{key}{subkey}[3] = 'stuff';        # won't work Instead, that must be written as:

        $tmp = $mldb{key};      # retrieve value
        $tmp->{subkey}[3] = 'stuff';
        $mldb{key} = $tmp;      # store value
[download]

This limitation exists because the perl TIEHASH interface currently has no support for multidimensional ties.