Yes but these were the typical combinations causing the errors:
1. 64 bit OS but only 32 bit Java installed
2. 32 bit OS (there was a bug with the launcher of the game, this is fixed now)
3. Multiple Java versions installed
4. No Java installed at all
Nearly every issue on the Steam forums related to this problem falls into one of those categories.
You said you uninstalled java completely. Did you also deleted the related folders (if any were remaining) manually? Also tried rebooting?