route53 client list_resource_record_sets fails with StartRecordType
**OS:** OS X Yosemite
**Python:** 2.7.6
**botocore:** 0.106.0

I'm trying to get the SOA records on a route53 hosted zone.  When I try to do so, it fails badly - I get the following response:

``` python
{'ResponseMetadata': {'HTTPStatusCode': 400, 'RequestId': '24865775-f4fb-11e4-a914-45b54a9f75e8'}, 'Error': {'Code': 'InvalidInput', 'Type': 'Sender'}}
```

This is further exacerbated in `exceptions.ClientError.__init__` when it looks for ['Error']['Message'] which doesn't exist in the InvalidInput error.

Here's the code I'm using:

``` python
>>> from boto3.session import Session
>>> sess = Session(region_name='us-east-1')
>>> r53 = sess.client('route53')
>>> zone = r53.list_hosted_zones_by_name(DNSName='example.com.')['HostedZones'][0]
>>> zid = zone['Id']
>>> r53.list_resource_record_sets(HostedZoneId=zid, StartRecordType='SOA')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/mike/venv/stacker/lib/python2.7/site-packages/botocore-0.106.0-py2.7.egg/botocore/client.py", line 199, in _api_call
    return self._make_api_call(operation_name, kwargs)
  File "/Users/mike/venv/stacker/lib/python2.7/site-packages/botocore-0.106.0-py2.7.egg/botocore/client.py", line 254, in _make_api_call
    raise ClientError(parsed_response, operation_name)
  File "/Users/mike/venv/stacker/lib/python2.7/site-packages/botocore-0.106.0-py2.7.egg/botocore/exceptions.py", line 300, in __init__
    error_message=error_response['Error']['Message'],
KeyError: 'Message'
```

diff --git a/botocore/parsers.py b/botocore/parsers.py
index 9e0b88554..8d27937b0 100644
--- a/botocore/parsers.py
+++ b/botocore/parsers.py
@@ -98,7 +98,7 @@ import logging
 
 from botocore.compat import six, XMLParseError
 
-from botocore.utils import parse_timestamp
+from botocore.utils import parse_timestamp, merge_dicts
 
 LOG = logging.getLogger(__name__)
 
@@ -705,7 +705,9 @@ class RestXMLParser(BaseRestParser, BaseXMLResponseParser):
         elif 'RequestId' in parsed:
             # Other rest-xml serivces:
             parsed['ResponseMetadata'] = {'RequestId': parsed.pop('RequestId')}
-        return parsed
+        default = {'Error': {'Message': '', 'Code': ''}}
+        merge_dicts(default, parsed)
+        return default
 
 
 PROTOCOL_PARSERS = {
diff --git a/tests/unit/test_parsers.py b/tests/unit/test_parsers.py
index 0901b195e..595b49978 100644
--- a/tests/unit/test_parsers.py
+++ b/tests/unit/test_parsers.py
@@ -306,6 +306,29 @@ class TestResponseMetadataParsed(unittest.TestCase):
         self.assertEqual(parsed['Error'], {'Message': 'Access denied',
                                            'Code': 'AccessDeniedException'})
 
+    def test_can_parse_route53_with_missing_message(self):
+        # The message isn't always in the XML response (or even the headers).
+        # We should be able to handle this gracefully and still at least
+        # populate a "Message" key so that consumers don't have to
+        # conditionally check for this.
+        body =  (
+            '<ErrorResponse>'
+            '  <Error>'
+            '    <Type>Sender</Type>'
+            '    <Code>InvalidInput</Code>'
+            '  </Error>'
+            '  <RequestId>id</RequestId>'
+            '</ErrorResponse>'
+        ).encode('utf-8')
+        parser = parsers.RestXMLParser()
+        parsed = parser.parse({
+            'body': body, 'headers': {}, 'status_code': 400}, None)
+        error = parsed['Error']
+        self.assertEqual(error['Code'], 'InvalidInput')
+        # Even though there's no <Message /> we should
+        # still populate an empty string.
+        self.assertEqual(error['Message'], '')
+
 
 class TestResponseParsingDatetimes(unittest.TestCase):
     def test_can_parse_float_timestamps(self):
['tests/unit/test_parsers.py', 'botocore/parsers.py']