The problem happens because by default the template system uses the formatted versions of columns, not the underlying "real" information. This is required in order to produce formatted values. However, that means that when using the template {pubdate:format_date(yyyy)}, the format_date function sees what is displayed in calibre, e.g. Jan 2013. Format_date calls a library function (not part of calibre) that tries to work out what the original date was given the formatted value. This function can fail in what seems to be arbitrary ways, in which case format_date will produce "BAD DATE". For example, the library function apparently cannot handle "Sep 2003" but can handle "May 2003".
You can avoid this problem by using a different template
Code:
program:format_date(raw_field('pubdate'), 'yyyy')
This template works because raw_field fetches the underlying value, not the formatted value.