Judging by the massive number of dependency issues (bugs, etc) that appeared in the bug history once they started working on moving to native menus, I guess it really was a time-consuming thing to fix :)
If the menu was already implemented in a generic (non-native) way for other OSes, then making a specific native implementation for one OS is more work and thus more time.
"I can't argue, but it's a time thing."
21 years later...
"Fixed."