This turned out to be quite a silly thing.
For the LYNC GAL to show contact information, as with everything else regarding lync, the E.164 format should be used in AD and the GAL for phone numbers.
In our case it was all normal 011 xxx xxxx etc… numbers.
Sadly it took me a good 2 hrs of searching to actually find the solution, very simple really.
Luckily the UC guy already did writeup on this, so he is saving me some time:
Once applied my contacts are showing details!