Why pssh command is not working?

Regarding the why, see /usr/share/doc/pssh/README.Debian.

To avoid any conflicts with the putty package, all of the programs have been
renamed.

parallel-ssh is pssh
parallel-scp is pscp
parallel-rsync is prsync
parallel-nuke is pnuke
parallel-slurp is pslurp

About that symlink, a slightly cleaner solution is creating /usr/local/bin/pssh symlink and let it point to /usr/bin/parallel-ssh. With the exception of /usr/local/ it is generally best to leave the content of /usr/ to the package manager. By default /usr/local/bin is too part of the PATH environment.

Try with parallel-ssh it has been renamed.

Quote from package description:

 The package contains:
 .
  - Parallel ssh (parallel-ssh, upstream calls it pssh), executes commands on
    multiple hosts in parallel
  - Parallel scp (parallel-scp, upstream calls it pscp), copies files to
    multiple remote hosts in parallel
  - Parallel rsync (parallel-rsync, upstream calls it prsync), efficiently
    copies files to multiple hosts in parallel
  - Parallel nuke (parallel-nuke, upstream calls it pnuke), kills processes on
    multiple remote hosts in parallel
  - Parallel slurp (parallel-slurp, upstream calls it pslurp), copies files
    from multiple remote hosts to a central host in parallel
 .
 These tools are good for controlling large collections of nodes, where faster
 alternatives such as gexec and pcp are not available.

Sometimes the name of the command used to start the program isn't the same as the name of the package that you installed to get said program.

I recently found this when I installed Maze of Galious to give it a go, it didn't show up in the Games menu and it took me a couple minutes to find out that to start the game I had to go to terminal and type 'mog'. /anecdote.

This could happen for variety of reasons, maybe the name (like in my anecdote) is too long to be a reasonable name for the command, maybe the name the developer wanted was already chosen, maybe the developer had brain-worms and just wanted to mess with you by calling it something totally random -- the why isn't worth worrying about, if you want to 'fix' it just use an alias or a sym/hard link.

If it bothers you that much you could submit a change request upstream, but if the developer chose that name s/he likely had a good reason.