euca-describe-instance returns error VolumeNotFound

euca-describe-instances has been working fine up until recently. We now see:

$ euca-describe-instances
VolumeNotFound: Volume vol-00000019 could not be found.

The logs on the nova-api server are as follows:

2012-04-05 03:14:05 DEBUG nova.auth.manager [-] Looking up user: u'xxxxx-yyyyy-zzz' from (pid=8961) authenticate /usr/lib/python2.7/dist-packages/nova/auth/manager.py:298
2012-04-05 03:14:05 DEBUG nova.auth.manager [-] user: User('bradm', 'bradm') from (pid=8961) authenticate /usr/lib/python2.7/dist-packages/nova/auth/manager.py:300
2012-04-05 03:14:05 DEBUG nova.auth.signer [-] using _calc_signature_2 from (pid=8961) _calc_signature_2 /usr/lib/python2.7/dist-packages/nova/auth/signer.py:139
2012-04-05 03:14:05 DEBUG nova.auth.signer [-] query string: AWSAccessKeyId=wwww-xxxx-yyyyy-zzzz%3Abradm_project&Action=DescribeInstances&SignatureMethod=HmacSHA256&SignatureVersion=2&Timestamp=2012-04-05T03%3A14%3A04Z&Version=2010-08-31 from (pid=8961) _calc_signature_2 /usr/lib/python2.7/dist-packages/nova/auth/signer.py:163
2012-04-05 03:14:05 DEBUG nova.auth.signer [-] string_to_sign: POST
91.189.93.65:8773
/services/Cloud/
AWSAccessKeyId=wwwwwww-xxxxxxx-yyyyyy-zzzz%3Abradm_project&Action=DescribeInstances&SignatureMethod=HmacSHA256&SignatureVersion=2&Timestamp=2012-04-05T03%3A14%3A04Z&Version=2010-08-31 from (pid=8961) _calc_signature_2 /usr/lib/python2.7/dist-packages/nova/auth/signer.py:165
2012-04-05 03:14:05 DEBUG nova.auth.signer [-] len(b64)=44 from (pid=8961) _calc_signature_2 /usr/lib/python2.7/dist-packages/nova/auth/signer.py:168
2012-04-05 03:14:05 DEBUG nova.auth.signer [-] base64 encoded digest: abcdefghijklmnopoqrstuvwxyz= from (pid=8961) _calc_signature_2 /usr/lib/python2.7/dist-packages/nova/auth/signer.py:169
2012-04-05 03:14:05 DEBUG nova.auth.manager [-] user.secret: wwwwww-xxxxxxx-yyyyyyy-zzzzz from (pid=8961) authenticate /usr/lib/python2.7/dist-packages/nova/auth/manager.py:343
2012-04-05 03:14:05 DEBUG nova.auth.manager [-] expected_signature: XQG93vpuCzepE5ZFHtRtMt5ljb06UB8VZs3XNOcABgU= from (pid=8961) authenticate /usr/lib/python2.7/dist-packages/nova/auth/manager.py:344
2012-04-05 03:14:05 DEBUG nova.auth.manager [-] signature: XQG93vpuCzepE5ZFHtRtMt5ljb06UB8VZs3XNOcABgU= from (pid=8961) authenticate /usr/lib/python2.7/dist-packages/nova/auth/manager.py:345
2012-04-05 03:14:05 AUDIT nova.api.ec2 [req-7e1a28db-b244-4788-9f09-2e1ae4ee8068 bradm bradm_project] Authenticated Request For bradm:bradm_project)
2012-04-05 03:14:05 DEBUG nova.api.ec2 [req-7e1a28db-b244-4788-9f09-2e1ae4ee8068 bradm bradm_project] action: DescribeInstances from (pid=8961) __call__ /usr/lib/python2.7/dist-packages/nova/api/ec2/__init__.py:435
2012-04-05 03:14:05 DEBUG nova.compute.api [req-7e1a28db-b244-4788-9f09-2e1ae4ee8068 bradm bradm_project] Searching by: {'deleted': False} from (pid=8961) get_all /usr/lib/python2.7/dist-packages/nova/compute/api.py:1010
2012-04-05 03:14:05 INFO nova.api.ec2 [req-7e1a28db-b244-4788-9f09-2e1ae4ee8068 bradm bradm_project] VolumeNotFound raised: Volume 25 could not be found.
2012-04-05 03:14:05 ERROR nova.api.ec2 [req-7e1a28db-b244-4788-9f09-2e1ae4ee8068 bradm bradm_project] VolumeNotFound: Volume vol-00000019 could not be found.
2012-04-05 03:14:05 INFO nova.api.ec2 [req-7e1a28db-b244-4788-9f09-2e1ae4ee8068 bradm bradm_project] 0.504622s 118.208.40.182 POST /services/Cloud/ CloudController:DescribeInstances 400 [Boto/2.2.2 (linux2)] application/x-www-form-urlencoded text/xml

Client tools version:
$ dpkg-query -W euca2ools
euca2ools 2.0.0~bzr516-0ubuntu3

Nova version:
$ dpkg-query -W nova-common
nova-common 2012.1~rc1~20120309.13261-0ubuntu1

Please let us know if there's anything else needed to diagnose whats going on.