The total change from the Windows 3.1 Start button to the subsequent Start buttons was making the Start menu a 2-column menu, putting the contents of the former Programs menu in the left pane and putting the rest of the Start menu items in the right pane. That's it. Oh, and making the initial view not show all the Programs items but only a subset, with an extra item at the bottom to show everything in the same form as it was under the Programs menu.
As for Win3.1 being complicated, every secretary I knew managed to get a handle on it within a few days so it couldn't have been that complicated. The only people I know of who couldn't figure out Win3.1 are the ones who to this day need repeated reminders of how to get to anything that's not directly on their desktop, so methinks the problem doesn't lie in Windows.
Um. You know that Windows 3.1 didn't actually have a Start Button, right?