If I recall correctly Fodor argued in Modules, Frames, Fridgeons, Sleeping Dogs, and the Music of the Spheres that this problem was in fact the heart of the AI problem

It depends on how general or narrow you make the problem. Compare: is classical decision theory the heart of the AI problem? If you interpret this broadly, then yes; but the link from, say, car navigation to classical decision theory is tenuous when you're working on the first problem. The same thing for the frame problem.