/usr/bin/pep8 is wrong here.  This is a continuation of what's in "message=" so it could be indented more than "message=".  Semantically, it looks like this:

``` python
AppError(
    name='PackageDBError',
    message=('Unable to save all information for'
        ' %(pkg)s: %(msg)s' [...])
```
but adding the extra parens is unnecessary here.

Since the arguments are short you could work around this by doing this:

``` python
                raise AppError(name='PackageDBError', message=
                    'Unable to save all information for %(pkg)s: %(msg)s' % {
                        'pkg': to_bytes(pkg),
                        'msg':to_bytes(response['message'])})
```
Which avoids juxtaposing the indentation for the parameter list with the proper indentation for the continuation of the string.
The hanging "message" isn't something I really like, though so it's debatable if we should do that just to shut up /usr/bin/pep8.

I think ignoring /usr/bin/pep8 here or adding the extraneous parenthesis is the right thing to do.