I have set up, on resource sheet, all of the resources to be used in my project plan. I have used the resource availability field to enter when users are on holiday (set units at 0% for the duration they are off, and back to 100% for their return).

Now, for example, a resource has been indicated as Project Manager resource for 1st November 2013 to 1st February 2014, but as they are on leave 1st - 7th December, they come up as being over-allocated as they are allocated as PM during the week they are off.

Is there any way I can get Project to ignore the period when their availability is set to 0%, or is there somewhere else I need to add their holidays in?

The holidays should be recorded as non-working time exceptions in the Resource's calendar. Changing a resources availability by manipulation of the max units does not automatically shift the task - it just flags the resource as overallocated.

Change the resource's calendars and Project will automatically shift the task so it is worked on only during working time.