When you look at your presence client does it go to "on phone" when you pick the receiver up? If it does not update then go to the Phone in CUCM and make sure the DN that is associated with that phone has a user assigned to it. Also did you check to make sure that the user in CUCM under System-Licensing-Capabilities Assignement had the presence option assigned to them?
I had this problem and I fixed it by assigning the user to the DN, however the main caveat is that I had multiple UDPs and I needed to make sure every one of them had the DN associated with them. Even if you are using one that looks setup correctly.