I've seen systems where the Recovery partition is not the same version of OS X as your main system. I haven't yet figured out how to upgrade the Recovery partition, but this is a problem we need to solve.
In the past I've had Recovery partitions go missing, and I use this tool to create a new one:
So in your case, you might need to delete your current Recovery partition (perhaps using
diskutil via the command line), then create a new Recovery Partition with the above tool.
However, I'm not comfortable suggesting you do this, so you might contact Apple about the issue first. Unless anyone else has a suggestion?