Why did you restart the server? You can just send SIGHUP to have it reload the file without restarting.
Appreciate it!
http://www.postgresql.org/docs/9.3/static/auth-pg-hba-conf.h... explains that you can just do a reload after changing pg_hba.conf.
http://www.postgresql.org/docs/9.3/static/config-setting.htm... explains more.