It is actually working. The problem is simply due to the current design of the paint tool:

If you move the mouse in a slice then the underlying segmentation slice is extracted and displayed. if press undo the extracted slice is still displayed, which is why is seems that the undo did not work.

This bug could not be fixed during the 2015.05 release.
Setting target_milestone to AfterNextRelease

Should be fixed for the upcoming release

The paintbrush tool works in a slightly different way than the other Segmentation tools:

It uses a own copy of the working slice in a separate Image, Contour and DataNode in addition to the one provided by the FeedbackContourTool. This is done to show the interactive drawing.The drawn outline doesn't consist of a single contour like in the other tools. Every drawn segment in the mouse move function is a own contour that is projected to the slice and than merged into the helper objects during the mouse move event to show the update. On undo only the contours of the feedback tool are cleared.

Suggested fix:

Restructure the tool to get rid of the additional objects. only use them for temporary displaying and not holding the data and fully clear them after drawing and use the objects from the FeedbackContourTool for displaying.

Pushed new branch T18602-paintbrush-undo.