The Calendars hold usually hold 4 years when they are set up and by default these are from 2011 to 2014.  A year must exist for leave to be booked into it.  This is a useful way of restricting leave being booked too far into the future.

To add a new calendar year you should go to Admin > Settings > Calendars (dropdown) > Your Calendars.  Click on the 'Working Year' calendar (usually called Default Working Year although you may have more than one) to open it and at the bottom of that page is the list of years added.  To add more, increase the 'Num Periods' (e.g. from 4 to 5) which will add 1 more year to the list below.  Open the newly added year to check the bank holidays are correct and add/remove/edit any Public Holidays where necessary.