I couldn't remove the previous version, not even with dpkg -r
--force-all so I removed with rm -rf from
/var/lib/dpkg/info/phpmyadmin.* and /usr/share/phpmyadmin.
Apt still wasn't able to install it properly so I removed it again
manually and install the .deb file with gdebi. Everything works fine now.
Also, got a vm with a fresh install and there weren't any issues, so you
can close this.