I recently implemented BGP graceful restart capability in a custom BGP app and encountered the same notification. By looking at the capabilities being advertised by the router, and advertising various subsets of those capabilities, I narrowed it down to the MPLS capability. It turned out the router deemed MPLS capability as a prerequisite for graceful restart. Adding the MPLS IPv4 unicast capability to the OPEN message along with the graceful restart capability fixed things for me.
Hope this helps. - Mike
