I found out that the reason why establishing trust didn't work was IPv6 stack. It wasn't fully configured on FreeIPA's side as we didn't use it but there were IPv6 DNS entries with AD domain controller name present. I remember that I read somewhere that you need to be able to reach all of the AD's DNS entries for trust to work. I can't find a link to that piece of information right now, though.
The steps I took to fix this problem were:
1) Disable IPv6 for currently used network interfaces in /etc/sysctl.conf with entries below and make these entries work by issuing sysctl -p command. You don't need (and should not) disable whole IPv6 stack as it is required by FreeIPA (again, read it somewhere but can't find the source).
net.ipv6.conf.lo.disable_ipv6 = 1 net.ipv6.conf.eth0.disable_ipv6 = 1 net.ipv6.conf.all.disable_ipv6 = 1 net.ipv6.conf.default.disable_ipv6 = 1
2) Configure directory server to use IPv4 only as described here:
http://gsr-linux.blogspot.com/2010/06/enforcing-directory-server-instances-t...
3) Restart ipa with ipactl restart
Then I was able to successfully establish trust to AD domain.