Are you using a 64 bit computer? The only binaries available on this website are 32 bit - so make sure you have the relevant 32 bit compatibility libraries installed (package name "ia32-libs" I think, but I don't use (K)ubuntu so I can't check this at the moment).
Or you can compile 64 bit TPT yourself: Source code is available by clicking on the relevant version at https://powdertoy.co.uk/Download/Browse.html and downloading powder-src.zip (source is also available on github). Some slightly out of date information about compiling is available on the wiki. The libraries you need installed are lua, fftw3, bz2, and SDL (-dev packages also required for them). From a terminal in the Powder Toy source folder, "make powder-64-sse3".