The /etc/hosts file was missing a line with the server's non-localhost IP and its hostname. Instead of letting it auto-detect all listen interfaces, fail, and give me an informative error, I had manually entered the non-localhost address as a listen address on domain setup.
I now added the missing line to /etc/hosts and let it auto-detect all listen interfaces - works.
This might be a different issue if it worked before. Please paste the contents of your /etc/hosts file just in case.
Also, try starting WebLogic with the -Djava.security.debug=jpspolicy flag and paste the output.
You might want to refer to this page: http://www.weblogic-tips.com/2011/07/07/error-related-to-opss-security-failing-while-starting-weblogic-servers/