Latest version of sys-apps/parted, that sys-apps/hal-0.5.10 can depend on is sys-apps/parted-1.8.7, but latest stable is sys-apps/parted-1.8.8. I haven't check if it works, but I think, that after trivial fixes in configure.in (for hal) it should (after revdep-rebuild). Now it's sort of broken anyway as if somebody has parted in world and hal depending on parted this will generate a block in emerge.
*** This bug has been marked as a duplicate of bug 190860 ***