I was missing something alright.
So, HMC 4.5 makes use of OAB (offline address Book) server pools, which is new in 4.5, however I was thinking that having to add OAB server's as a resource was not in 4.0, but it is.
Go to your MPS/HMC server, and add an OAB server by using provtest C:\program files\Microsoft Hosting\Provisioning\Samples\Exchange OAB Resource Manager\AddOABServer.xml (I think that path is right, should be close enough to get you where you need to be) - obviously after modifiying the file to account for your Exch server name and domain controller.
This worked wonders for me - hope it helps the original poster.
Scott