端末を起動して以下を実行してみてください。

$ sudo sed -i "s/NoDisplay=true/NoDisplay=false/g" /etc/xdg/autostart/*.desktop

自動起動アプリの設定画面を開いてみてください。
以前この画面を開いてたとしたら、だいぶ項目が増えたはずです。
その中に「アップデート通知」update-notifierという項目があって、かつ有効になってるはずです。
これのことかと思いますよ。
もし常駐してるようならそういうことなのかもしれませんね。