Joel-
Thank you for your feedback. If you are entering the shortcode into the “Visual” editor, be careful that you are not putting the start/stop tags inside of a paragraph. WordPress’s WYSIWYG editor has a tendency to strip paragraph tags. Personally, I use the “Text” editor. I just tested on a page in 3.6 without issue with a paragraph tag. If you are comfortable with the text editor, give this a try:
[userloggedin]<p>Paragraph Text</p>[/userloggedin]
It should work as intended. If you still have an issue, please be more precise as to which version of WordPress you are using and exactly how you are utilizing the shortcode.
Thank you!