Find their biggest objection and their primary decision maker. You mentioned in a acomment security is a concern for them. Argue that using amazon is far more secure than their system (which is likely true). See aws compliance here: http://aws.amazon.com/compliance/