I also can't get native runtime working. After doing
> cd ~/.local/share/Steam/ubuntu12_32
> LD_LIBRARY_PATH=".:${LD_LIBRARY_PATH}" ldd $(file *|sed '/ELF/!d;s/:.*//g')|grep 'not found'|sort|uniq

I got the output containing
> libdbus-glib-1.so.2 => not found
> libgconf-2.so.4 => not found
> libnm-glib.so.4 => not found
> libnm-util.so.2 => not found
> libudev.so.0 => not found

Maybe that's an issue, but I don't think so - on my previous Archlinux
installation the game wouldn't start with all those libraries present.
Basically, my Linux installations' configurations were mostly the same.