Strange Pagination 404 Error

Hi!

I have a Site where there is a Page as Overview for my Projects:
http://longplayer.net/lets-play/

now i would like to have pretty permalinks what i was making with the following Permalink Structure:

/lets-play/%category%/%postname%

and it works good so far but now i was adding a pagination like this:

http://pastebin.com/mBbvA5PK

i call the funtion like this:

<?php echo pagination(2, true, true); ?>

Works fine on the Mainpage, Tags, Search but not for Categories, first Page is showing no problem but all behind that, are not showing…

I read the Codex and try Troubleshot it, its not a Error caused by any Plugin. I was reading it could be a Problem with the page named likely but rename it and regenerate the Permalinks didnt help either…

if i change the permalink structure to just:
/%category%/%postname%
it works, so i tryed to make it look pretty again with the category base but this dont get me the permalinks i would like to have…

so how do i make it happend to have the site:
http://longplayer.net/lets-play/

and use:
http://longplayer.net/lets-play/category/postname
for my posts? i was thinking about rewrite rules maybe?! i use nginx as webserver… any help is much appreciated i was wrapping my head about this for several days now and cant get any further…