Failed to import appliance /home/rene/Descargas/MusicBrainz NGS 2012-01-12.ova. Could not find a valid medium format for the target disk '/home/rene/VirtualBox VMs/vm/musicbrainz-server-2012-01-12-disk1.vmdk.gz'.
The thing is that this appliance was generated by vmware with gzip compression enabled for the vmdk disk. I don't know whether there's another workaround, but it turns out that the .ova file is in fact a tar file so :
tar -xvf MusicBrainz\ NGS\ 2012-01-12.ova gzip -d musicbrainz-server-2012-01-12-disk1.vmdk.gz
And you're all set.