Fail2ban cannot work properly with Ubuntu 9.04 Server as Ubuntu installed with Python 2.6. It is very easy to overcome this problem.
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install python2.5
sudo nano /usr/bin/fail2ban-server
Change the first line from
/etc/fail2ban/jail.conf as usual.
sudo /etc/init.d/fail2ban restart