All reports of symlink-should-be-relative for the archive. The extended description of this tag is:
Symlinks to files which are in the same top-level directory should be relative according to policy. (In other words, a link in /usr to another file in /usr should be relative, while a link in /usr to a file in /etc should be absolute.)
If you use debhelper, running dh_link after creating the package structure will fix this problem for you.
Refer to Debian Policy Manual section 10.5 (Symbolic links) for details.
This tag has not been emitted in any package tested by Lintian.