[Mordekay]

already did that, but 2 things i have to say:
1. the first startup on your second post looks fine to me. For me the server is running there.
2. ./hlds_linux? I always started my server with ./hlds_run. The engine should then use the appropriate binary itself.
Other than that i have no idea what's wrong with the server, but i have to say that i don't use ReHLDS. Imo it should be banned here as it violates the license agreement of Valve.