I’m running 1.0.11 too. Also Linux, Apache, and MySQL.
I am using the built-in SEF in Joomla.
The reason I was asking for your specs was I found this thread:
http://forum.joomla.org/index.php?PHPSESSID=02c0da39868c8c4b4e7862fd5f90ee82&topic=67144.0
at the Joomla.org forums that describes this problem as a bug in 1.0.9. I was hoping you were running that. 😀
I would recommend turning off ARTIO JoomSEF v1.3.1 and try the Core SEF in Joomla. If that cures the problem that you might check the with the developer of ARTIO JoomSEF v1.3.1 to see if they have a fix.
Sorry I wasn’t more help.