I have since figured out my own answer. I can reproduce it with the following process:
1) Settings > Security > Screen lock > put in current pattern > Select Pattern > Note that "Require pattern to start device" is checked
2) Make no changes and back out to Settings (or press home and re-open Settings)
3) Go to Accessibility
4) Turn on any Accessibility Service (I turned on Pushbullet but it doesn't seem to matter what service you do)
5) Follow step 1 until you see that "Require pattern to start device" is unchecked.
In the Android M Preview 2, turning on Push Bullet prompted me with "If you turn on Pushbullet, your device won't use your screen lock to enhance data encryption" and pressing ok brought me to a screen where I needed to enter my current pattern. The text reads "Because turning on Pushbullet affects data encryption, you need to confirm your pattern." I do not remember this screen in 5.0 or 5.0.1 but I believe this is what was causing it.