Well, I haven't actually used Fail2ban, but technically, iptables (which is called by Fail2ban) will work with either hostname or IP address, though using names is a bad idea since DNS resolution may fail or be very slow.
According to this
HOWTO, Fail2ban passes either hostname or IP address to iptables which creates the appropriate rule.
To get round any hostname resolution issues, you'll have to look for an option either in the daemon being protected (e.g. sshd) to log IP addresses not hostnames (preferable, I would think), or in Fail2ban to do a DNS lookup before passing to iptables (I'm not sure if this is possible).
For example, in your sshd_config file (I think the default is supposed to be /etc/ssh/sshd_config), there should be an option called 'UseDNS', which defaults to 'yes'. This causes sshd to resolve IP addresses (and check the hostname maps back to the IP address). Given the ease with which addresses can be spoofed, even to one matching an real host, and since you're using Fail2ban as your primary defence mechanism, you should consider setting this option to 'no'.