First the picture was set wrong in both Outlook and Lync 2010. I used CodeTwo Active Directory Photos to remove and readd the picture which fixed the problem in Outlook. 

I tried to remove c:\users\username\appdata\local\microsoft\communicator\sip_%username%@domain\galcontacts.db and galcontacts.db.idx which didn't update anything (except recreate the cache files). 

Note: The same user has issues with the GAL taking extremely long to update. 

Hi

Is this happening for all the users. check this

http://iconraja.wordpress.com/2010/12/20/forcing-active-directory-photos-with-lync-2010/

Forcing Gal for particular User

http://policelli.com/blog/archive/2011/03/16/how-to-force-an-address-book-refresh-on-lync-client/ 

Hello,

This is not happening for all users but used link #1 and assigned the policy just to that one user. After going through the steps I realized this is just making the user not be able to set a custom picture hosted on the internet (as far as I know). I also tried to force GAL update for the user which didn't work as well.

Thanks for the response.

Is it possible that uploading pictures through CodeTwo Active Directory Photos is the problem?

It is possible.

You can check it here.

In order to be able to view users' Active Directory photos in Lync, end-users have to choose to use the Default corporate picture in Lync Client's photo options.

Not that the picture must be less than 10kb in size, and preferably 96px by 96px.

Note: Microsoft is providing this information as a convenience to you. The sites are not controlled by Microsoft. Microsoft cannot make any representations regarding the quality, safety, or suitability of any software or information found there. Please make sure that you completely understand the risk before retrieving any suggestions from the above link.

I have CodeTwo installed already and use it regularly to upload Outlook/Lync photos. I did resize the picture so it is 1 KB and 96px by 96 px. 

I haven't noticed any change so far. I will try to use the force GAL trick by removing galcontacts.db and galcontacts.db.idx once I see the user.

It has not worked so far (1 hr later). I force replicated (Seems like it could help).