This generally appears to be the case of an epoch being omitted, and therefore presumed 0, when it is not actually 0. While there are ~100 such cases in the distros I am parsing (debian-6, 7 and 8), they reduce to the 17 unique cases I have appended to this email.
Thank you for keeping up this good work, and I hope this information will be helpful.
'debian-8': name 'dovecot', version : '1.2.15', release : '1', epoch: '1' conflicts with epoch: '0'.
'debian-8': name 'libav', version : '0.8.3', release : '1', epoch: '4' conflicts with epoch: '6'.
'debian-8': name 'libav', version : '11.6', release : '1~deb8u1', epoch: '0' conflicts with epoch: '6'.
'debian-8': name 'phpmyadmin', version : '4.2.6', release : '1', epoch: '0' conflicts with epoch: '4'.
'debian-8': name 'rar', version : '3.7b1', release : '1', epoch: '0' conflicts with epoch: '1'.
'debian-7': name 'dovecot', version : '1.2.15', release : '1', epoch: '1' conflicts with epoch: '0'.
'debian-7': name 'libav', version : '0.8.3', release : '1', epoch: '4' conflicts with epoch: '6'.
'debian-7': name 'rar', version : '3.7b1', release : '1', epoch: '0' conflicts with epoch: '1'.
'debian-6': name 'dovecot', version : '1.2.15', release : '1', epoch: '1' conflicts with epoch: '0'.
'debian-6': name 'kdegraphics', version : '3.5.0', release : '3', epoch: '4' conflicts with epoch: '0'.
'debian-6': name 'kdegraphics', version : '4.0', release : '', epoch: '4' conflicts with epoch: '0'.
'debian-6': name 'kdelibs', version : '3.5.10.dfsg.1', release : '2.1', epoch: '4' conflicts with epoch: '0'.
'debian-6': name 'kdelibs', version : '3.5.10.dfsg.1', release : '5+deb6u1', epoch: '0' conflicts with epoch: '4'.
'debian-6': name 'nbd', version : '2.9.16', release : '8+squeeze2', epoch: '0' conflicts with epoch: '1'.
'debian-6': name 'rar', version : '3.7b1', release : '1', epoch: '0' conflicts with epoch: '1'.
'debian-6': name 'xfig', version : '3.2.5.b', release : '1.1', epoch: '0' conflicts with epoch: '1'.
'debian-6': name 'zodb', version : '3.9.4', release : '1.1', epoch: '0' conflicts with epoch: '1'.