It could be happened in an Exchange 2010 transition. To resolve this, add a public folder replica to the new server from the old one.
If this doesn’t solve try out this….
Try to convert the address lists to 2010 and reseting the OAB directory, enabling web based distribution and fixing up the autodiscover.
Please update me about further progress !