I tried installing partimage on a different computer with VL5.9 standard and I still get the same error.
I use Gslapt to install as I'm still rather new to linux but learning fast, perhaps you use some terminal wizardry to install, could that be why it works for you and not me?. Not one to be easily beaten I tried compiling newt but got errors that I was unable to resolve due to my lack of experience.
I then found a slackware package of newt from here http://www.slackware.com/~alien/slackbuilds/newt/pkg/12.0/
which I installed and now partimage works. The slackware newt package is a massive 167K so much bigger than the newt in the repository. I know you say newt in the repository is fine and should be 9.1K but if I look inside slackware newt package then I can see libnewt.so.0.52, the file partimage can't find, but I can't see this file in the vector repository newt. If you think there is anything else I should try let me know and I'll give it a go.
Perhaps someone else will be along shortly to try partimage and at least confirm if there is something wrong with the package or if it's just something I'm doing.