I can confirm the same problems, with the same involved versions.
For me the problem was solved by explicitly asking for the package libparted0 to be installed, causing the removal of the packages libparted-2.1-0 and libparted1.8-12.
Looks like the result of the package name change, which happened with parted 2.2-1. I guess apt couldn't manage to figure out that upgrade on its own.
I can confirm the same problems, with the same involved versions.
For me the problem was solved by explicitly asking for the package libparted0 to be installed, causing the removal of the packages libparted-2.1-0 and libparted1.8-12.
Looks like the result of the package name change, which happened with parted 2.2-1. I guess apt couldn't manage to figure out that upgrade on its own.