Please test with the below patch. If see any problem in this patch please let me know. Thanks.

=== modified file 'nova/api/ec2/__init__.py'
--- nova/api/ec2/__init__.py	2011-01-27 22:10:42 +0000
+++ nova/api/ec2/__init__.py	2011-01-29 00:03:03 +0000
@@ -171,7 +171,7 @@
                     req.path)
         # Be explicit for what exceptions are 403, the rest bubble as 500
         except (exception.NotFound, exception.NotAuthorized) as ex:
-            LOG.audit(_("Authentication Failure: %s"), ex.args[0])
+            LOG.audit(_("Authentication Failure: %s"), utils.utf8(ex))
             raise webob.exc.HTTPForbidden()
 
         # Authenticated!
@@ -316,30 +316,31 @@
         try:
             result = api_request.invoke(context)
         except exception.InstanceNotFound as ex:
-            LOG.info(_('InstanceNotFound raised: %s'), ex.args[0],
+            LOG.info(_('InstanceNotFound raised: %s'), utils.utf8(ex),
                      context=context)
             ec2_id = cloud.id_to_ec2_id(ex.instance_id)
             message = _('Instance %s not found') % ec2_id
             return self._error(req, context, type(ex).__name__, message)
         except exception.VolumeNotFound as ex:
-            LOG.info(_('VolumeNotFound raised: %s'), ex.args[0],
+            LOG.info(_('VolumeNotFound raised: %s'), utils.utf8(ex),
                      context=context)
             ec2_id = cloud.id_to_ec2_id(ex.volume_id, 'vol-%08x')
             message = _('Volume %s not found') % ec2_id
             return self._error(req, context, type(ex).__name__, message)
         except exception.NotFound as ex:
-            LOG.info(_('NotFound raised: %s'), ex.args[0], context=context)
-            return self._error(req, context, type(ex).__name__, ex.args[0])
+            LOG.info(_('NotFound raised: %s'), utils.utf8(ex), context=context)
+            return self._error(req, context, type(ex).__name__, utils.utf8(ex))
         except exception.ApiError as ex:
-            LOG.exception(_('ApiError raised: %s'), ex.args[0],
+            LOG.exception(_('ApiError raised: %s'), utils.utf8(ex),
                           context=context)
             if ex.code:
-                return self._error(req, context, ex.code, ex.args[0])
+                return self._error(req, context, ex.code, utils.utf8(ex))
             else:
-                return self._error(req, context, type(ex).__name__, ex.args[0])
+                return self._error(req, context, type(ex).__name_,
+                                   utils.utf8(ex))
         except Exception as ex:
             extra = {'environment': req.environ}
-            LOG.exception(_('Unexpected error raised: %s'), ex.args[0],
+            LOG.exception(_('Unexpected error raised: %s'), utils.utf8(ex),
                           extra=extra, context=context)
             return self._error(req,
                                context,

=== modified file 'nova/utils.py'
--- nova/utils.py	2011-01-27 19:52:10 +0000
+++ nova/utils.py	2011-01-28 23:45:43 +0000
@@ -405,6 +405,12 @@
     """
     if isinstance(value, unicode):
         return value.encode("utf-8")
+    if isinstance(value, Exception):
+        if value.args:
+            return value.args[0].encode("utf-8")
+        else:
+            return ""
+
     assert isinstance(value, str)
     return value