Fast Dials are indeed an IP Phone Service. This service must be configured on CallManager. Go to: "Feature > Cisco IP Phone Services > Add a New IP Phone Service". Then, go to: "Help > For this page" to get further definitions of the fields that are required for entry.
Once the service is configured, it must then be assigned to the device. On the Phone Configuration sub-menu, go to: "Subscribe/Unsubscribe Services > Subscribe a New Service", you should then see the newly configured fast dial phone service in the drop-down box. As you will see, a user is directly tied to these services. The entries you make for the user here must match exactly to the entries made for them in the User Profile menu, otherwise the feature will give an error when it is accessed. Good luck.