Could you please try to install fresh Joomla with sample data and JoomSEF 4.3.0 on your host to see if it happens too?
Could you also post some system information about your host? Like what server it runs (Apache? which version?), whether it runs Linux or Windows, etc. Thank you.

I did a fresh install and it works fine.
Apache 2.2.22
MySQL 5.0.92
OS: linux x86_64

Just test it on my localhost server on linux with php 5.3.x and the problem persists. Somwhere, I guess, it is a problem between extensions...
The website is running PhocaGallery, PhocaGUestbook, Falang, aiContactSafe, Acymailing, Jcomments...

I found the problem!

I'm using JA T3 Framework for my template and this causes the problem. I did a fresh install of joomla with joomsef4.3 and t3framework-blank and everything is working fine...
So when I create the template I changed something that now conflicts with Joomsef4.3.0.

EDIT: Nope! It's not that the problem. I've disabled all the modules on the live website and the page is loading.

EDIT2: The real problem is a module that displays a menu which have only menu item aliases. So the new version of joomsef it's not handling menu aliases? The line error was exactly at this point.

Line 187: // Get aliased menu item
...but on a fresh install with t3 and joomsef4.3 the menu item alias works :/

The difference between JoomSEF 4.3.0 and 4.2.9 with menu item aliases is that 4.3.0 can handle more than one level of alias nesting.

So 4.2.9 only followed one level of menu aliases, but with 4.3.0 if menu item alias points to another alias and that points to another, JoomSEF tries to follow them until it finds a menu item which is not an alias.
So theoretically, if you have a loop in your aliases, it can hang JoomSEF for forever (until the time limit exceeds). So check if all your aliases point to correct menu items, you can't have a structure like:
Menu1 -> alias to Menu2
Menu2 -> alias back to Menu1

This will stop JoomSEF 4.3.0 from working.

I don't know why but the first item from this menu was pointing back to him.. So this was the problem.

Thank you so much!!
[Problem Solved]