Hello,
seems like some security constrains for your Joomla! installation. Doesn't either really seems this would be connected directly to JoomSEF or its installation.
What about the safe_mode for your installation? Seems it is on, maybe switching it to off would help you.
Best regards,
Jirka