I had the same or a similar error to what you see. The issue was for me (and I think is likely the same for you) that I had an older local tiled installation, built from source.
This installed a version of `libtiled.so` which get's looked up by the newer tiled, but doesn't work with it, so you should cleanly uninstall the source-built tiled, completely (`make uninstall` in you old source dir). You can find the offending lib, by doing `ldd /usr/bin/tiled`. In short, this is not a bug in the packaged tiled.
