Update Manager reports file not found (404)

The most recent run of Update Manager contained 79 updates. It kept failing with "404 file not found" until I removed the rsyslog update (suggested by the details page for the error). It then completed successfully, and notified me of the one outstanding update, which was for rsyslog. When I accepted the update request, it failed with the same error.

ProblemType: Bug
DistroRelease: Ubuntu 12.04
Package: rsyslog 5.8.6-1ubuntu8.1
ProcVersionSignature: Ubuntu 3.2.0-43.68-generic 3.2.42
Uname: Linux 3.2.0-43-generic x86_64
ApportVersion: 2.0.1-0ubuntu17.3
Architecture: amd64
Date: Sat Jun 15 12:55:49 2013
InstallationMedia: Ubuntu 12.04 LTS "Precise Pangolin" - Release amd64 (20120425)
MarkForUpload: True
ProcEnviron:
 LANGUAGE=en_GB:en
 TERM=xterm
 PATH=(custom, no user)
 LANG=en_GB.UTF-8
 SHELL=/bin/bash
SourcePackage: rsyslog
UpgradeStatus: No upgrade log present (probably fresh install)