Finally I was able to solve this problem, here is how?
Sample URL for file on Amazon S3 is-
http://adminportal.s3.amazonaws.com/sample.pdf?AWSAccessKeyId=AKIAIRUZSRRCVSLXZCIA&Expires=1372653478&Signature=RvMJ1gJL+qNKmnRkqzuytmlUTGQ=
Here the Signature is generated by classes provided by Amazon.
For unknown reasons, 'Force.com for Amazon Web Services' app was generating signature which contain SPACES.
E.g. In the given URL, space is replaced by '+'.
To get rid of the problem, just URL encode the signature. Encoding will replace spaces with special character and problem will be resolved.