This is one of those problems that I regularly come across and it catches me out over and over again. Yesterday, yet again, I was scratching my head at yet another disabled ribbon button and thinking "why oh why didn't I document how I fixed this last time!".
The funniest part is 9 times out of 10 the solution is ridiculously straight forward. Just republish your solution! For some reason I have not yet quite figured out, maybe it's down to something funny happening in the cache, but a simple republish gives CRM the appropriate kick up the bottom it needs to get that button enabled.
Afterthought - if you're a developer, and haven't yet done so, download and use Ribbon Workbench here. Quite simply, it's just pure awesome.