Where is the UI menu option for "Separate by loose parts"?
Make sure that you're presing P in edit mode, not object mode.
If that doesn't work you can find the separate action here (Mesh > Vertices > Separate > By loose parts):



You can check if the configuration is right on File > User Preferences > Input and search for "separate" and look on "mesh":