I've found that fail2ban fails to parse date strings and shows errors:
2006-04-29 17:25:38,807 ERROR: time data did not match format: data=Apr 29 06:26:49 fmt=%b %d %H:%M:%S 2006-04-29 17:25:38,809 ERROR: Please check the format and your locale settings.
"data=Apr 29 06:26:49" means timeregex works. However, the timepattern does not look incorrect...
According to a bug report in BTS, locale setting causes this issue. Add a line that follows to /etc/default/fail2ban
export LANG=C