I've used this primitive several times, and followed the same process you outlined below. It has always seemed to work, unless I used a bad RegEx or misspelled the name of the key.
If you look in the System Rules - Failed section of the Audit results, and then click on the link labeled "failed" under Results, it may provide a bit more information. You may also try creating the check but not specifying a platform or label.
One last suggestion would be to export the check, then run the Check.xml you've exported using the Policy Auditor CLI. i.e. engineMain.exe –m oval –i Check.xml –f –o results.xml
Enginemain is found in the ..\Policy Auditor Agent\Engine directory. The results.xml will provide some debug-level output on the execution of the check, which may help you figure out which part of the check is causing the 'fail' result.
Hope that helps!