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