You cannot add items to a list (usually what is meant when you say "respond to a Sharepoint survey") with only Read permissions. Users will need either Contribute permissions or a custom permission level that includes Add Items. It is also important to distinguish the site or list that you're setting permissions for: when you say that you have "contribute access", you may only have set Contribute permissions for your site. You need to set it for the list that contains the survey results.
Lists usually inherit permissions from their parent sites, but it is often prudent to stop inheriting and set custom permissions on lists (like surveys) that everyone will need to contribute to. That will keep users in other directorates/groups/teams from mucking with the Shared Documents library (and many other things) of whatever directorate/group/team is hosting the survey.
Lists can be set up to handle access requests so that the "access denied error message" you received will include a link to request access. This may be a feature to consider on your survey to simplify the resolution of future permission errors.