OKAY! Found the answer.
In the code of our EditorInitialized event handler:
var __e_Editor_EditorElement = e.Editor.EditorElement;
__e_Editor_EditorElement.SelectedValue = ((PropertyGridItem) e.Item).Value;
Something like the Digit project example: SelectedValue.GetType() and PropertyGridItem.Value.GetType() were both Int32.
Our example was a little bit different in that the object backing the PropertyStoreItem itself was the complex object and not a primitive. So we ended up with something like typeof(Guid) != typeof(OurObject).
When I exposed a reference to the complex object this reference, this all cleared up and I got the PropertyChanged event from the PropertyStoreItem like I expect.
Hope this helps someone.