The issue is that deb_checkmd5sums tries to use prelink to compute the checksums if present:

    MD5SUM="$PRELINK -y --md5"

However the script then adds the -c option for its main loop:

$MD5SUM -c 2>&1 | $SED -e "s/^.*md5sum: MD5 check failed for '\(.*\)'/DIFF \1/; s/^.*md5sum: can't open \(.*\)/ERR \1/" | {
while read file err

The problem is prelink does not have a '-c' option, causing it to only report an error:

$ echo 1234 /usr/sbin/prelink | prelink -y --md5 -c
/usr/sbin/prelink.bin: option requires an argument -- 'c'
Try `prelink.bin --help' or `prelink.bin --usage' for more information.

As a result the main loop does not check the MD5 checksums at all. Instead it runs twice, first with file="/usr/sbin/prelink.bin:" and then with file="Try".

As far as I can tell, the issue that triggered the use of prelink (Debian bug #445531) no longer exists so that computing the MD5 checksums the normal way works just fine.

So I propose the attached patch.