Found another bug - or I guess it's more of a compatibility issue than a bug.
In any case, Atahualpa 3.6.1 seems to ignore the All-in-one SEO pack's "Menu Label" option - it pulls the menu label from the post/page title instead.
I tried playing with plugin setting to make sure it's not All-in-one that's causing it, but it wasn't until I reverted to Atahualpa 3.5.3 that the issue was gone. Reverted back to 3.6.1 and it came back
Thanks JD and Flynn for posting updates so quick. You guys are like superheros