I've upgraded to karmic now. Still no icons that let's me know I have available updates...

$ apt-cache policy update-notifier
update-notifier:
  Installed: 0.87
  Candidate: 0.87
  Version table:
 *** 0.87 0
        500 http://se.archive.ubuntu.com karmic/main Packages
        100 /var/lib/dpkg/status

$ update-notifier --debug-updates
(update-notifier:3158): update-DEBUG: update_check()

(update-notifier:3158): update-DEBUG: /usr/lib/update-notifier/apt-check returned 94 (security: 0)
(update-notifier:3158): update-DEBUG: is_package_system_locked: 0
(update-notifier:3158): update-DEBUG: interval_days from gconf: 7

(update-notifier:3158): update-DEBUG: last_launch from gconf: 1252354686 (Mon Sep  7 22:18:06 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/dpkg.log: 1252355061 (Mon Sep  7 22:24:21 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/dpkg.log: 1252355061 (Mon Sep  7 22:24:21 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/dpkg.log: 1252355061 (Mon Sep  7 22:24:21 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/dpkg.log.1: 1251756854 (Tue Sep  1 00:14:14 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/dpkg.log.1: 1251819204 (Tue Sep  1 17:33:24 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/dpkg.log.1: 1252355061 (Mon Sep  7 22:24:21 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/dpkg.log.2.gz: 1248440224 (Fri Jul 24 14:57:04 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/dpkg.log.2.gz: 1251819204 (Tue Sep  1 17:33:24 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/dpkg.log.2.gz: 1252355061 (Mon Sep  7 22:24:21 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/dpkg.log.3.gz: 1246138509 (Sat Jun 27 23:35:09 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/dpkg.log.3.gz: 1251819204 (Tue Sep  1 17:33:24 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/dpkg.log.3.gz: 1252355061 (Mon Sep  7 22:24:21 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/apt/term.log: 1252355062 (Mon Sep  7 22:24:22 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/apt/term.log: 1252355062 (Mon Sep  7 22:24:22 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/apt/term.log: 1252355062 (Mon Sep  7 22:24:22 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/apt/term.log.1.gz: 1251705770 (Mon Aug 31 10:02:50 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/apt/term.log.1.gz: 1251819194 (Tue Sep  1 17:33:14 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/apt/term.log.1.gz: 1252355062 (Mon Sep  7 22:24:22 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/apt/term.log.2.gz: 1248440225 (Fri Jul 24 14:57:05 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/apt/term.log.2.gz: 1251819194 (Tue Sep  1 17:33:14 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/apt/term.log.2.gz: 1252355062 (Mon Sep  7 22:24:22 2009
)

(update-notifier:3158): update-DEBUG: mtime from /var/log/apt/term.log.3.gz: 1246138510 (Sat Jun 27 23:35:10 2009
)

(update-notifier:3158): update-DEBUG: ctime from /var/log/apt/term.log.3.gz: 1251819194 (Tue Sep  1 17:33:14 2009
)

(update-notifier:3158): update-DEBUG: last_launch from /var/log/apt/term.log.3.gz: 1252355062 (Mon Sep  7 22:24:22 2009
)

(update-notifier:3158): update-DEBUG: time now 1252355587 (Mon Sep  7 22:33:07 2009
), delta: 525