Simple REST API server
I'd write the error handling this way:

def render(self, request):
    operations = {
        'POST': 'create',
        'GET': 'read',
        'PUT': 'update',
        'DELETE': 'delete',
    }
    if request.method not in operations:
        response = {
            'success': False,
            'error': 'InvalidRequestMethod',
            'error_message': ("Valid request methods: %s" % (', '.join(operations.keys()))),
        }
        request.setResponseCode(http.NOT_ALLOWED)
    else:
        response = {'success': True}
        ...
    return json.dumps(response)


Note the changes:


Since the error handler is simpler than the main processing code, put it first to get it out of the way.
if request.method not in operations reads better than if request.method not in operations.keys() and might be slightly more efficient.
Reuse operations.keys() for the error message.
Set HTTP status 405 ("Method Not Allowed").  (The constant is in twisted.web.http.)


In KeyValueStorage, I suggest raising the standard KeyError instead of making your own exception classes.