You can do this with ImageMagick and this helper script. The script only splits the image vertically, but that's fine — we can rotate the resulting strips by 90 degrees and try again.
(This is all assuming that you're working on Linux, Mac OS X or some other Unix-line OS, since the script is a Unix bash shell script. If you're on Windows, I suppose you could try running it under Cygwin. And, of course, you obviously need to have ImageMagick installed, although if you're using Linux there's a good chance that you already do.)
Specifically, if you've saved the image in your question as
spritesheet.png and the script as
divide_vert in the current directory, and made the script executable with
chmod 755 divide_vert, the following shell commands ought to do the job:
./divide_vert -i spritesheet.png line-%02d.png
montage line-*.png -rotate 90 -geometry '1x1<' -tile 1x -background none joined.png
./divide_vert -i joined.png sprite-%03d.png
mogrify -rotate 270 sprite-*.png
montage command is a bit tricky, since it does two things at the same time: rotating the lines by 90 degrees clockwise and joining them into a single tall strip so that we can split them all with just one more call to the script. The funny-looking
-tile options tell
montage not to resize the source images, as it would normally do, and to arrange them in a single vertical column. For more information about how they work, see this page.
divide_vert pass will probably take a bit more time than the first. Just give it half a minute or so and it should be done. All the other steps should be pretty quick.
montage command is also handy for creating sprite sheets, as in this answer on the Game Development Stack Exchange.
Pps. I'm sure there are other ImageMagick scripts out there that can do the job, this was just the first one I found. Another one, which has more features and can do the entire job in one pass, is this one called "multicrop". Unfortunately, for this task, the multicrop script is perhaps a bit too advanced: you need to disable the unrotation feature and reduce the grid spacing down to 1 to get the expected results, and even then it's a bit too zealous in splitting up the sprites, such that e.g. the few disconnected pixels below the jumping sprite get split into a separate image. It's also rather slow if you have a lot of sprites on the sheet.