I use primefaces 3.5 with pretty faces 3.3.3 and works ok. The configuration in your web.xml seems to be ok. Make sure you place pretty-config.xml also in WEB-INF. About the pretty-config you posted: it doesn't make any sense to have a url-mapping where the pattern and the view-id are the same, so remove it. Also I don't have that rewrite rule, I have several mappings like the folowing:
<url-mapping id="login">
<pattern value="/login/">
<view-id value="/login.jsf" />
</url-mapping>
Did you try removing that rewrite rule to see what happens?