Version:            (using KDE KDE 3.5.6)
Installed from:    Debian testing/unstable Packages

This is reported in Debian BTS at http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=350763

I quote the end of page 6 from
/usr/share/doc/kde/HTML/en/kdvi/KDVI-features.dvi.gz:

<quote>
Warning. 
On some installations, the hyperref macro package is configured to
generate PostScript hyperlinks for dvips by default. On these 
systems, using the line

\usepackage{hyperref}

will generate DVI file whose hyperlinks are not visible in KDVI. 
Worse, KDVI will call the ghostview PostScript interpreter for every
page, which makes the display very slow.
</quote>

For me, KDVI properly displays dvips hyperlinks.  I haven't noticed
that the display is slow either.

Therefore the warning may not apply any more.