That might be because the upgradeable packages are in fact kept back. Can you confirm? Is this in Dapper or Edgy? -- wrong notification for upgradeable packets https://launchpad.net/bugs/48613