The resolution depends on the version of Storm you're running.
[EDIT]
Storm 0.9.1 has just been released today (22nd Feb 2014): release notes mention zeroMQ dependencies are now by default replaced by Netty
The installation instructions of the previous version (I successfully used those for 0.8.2 in the past) are here, they indeed mention zeroMq and jzmq as dependencies:
https://github.com/nathanmarz/storm/wiki/Setting-up-a-Storm-cluster
The installation instructions of 0.9.0.1 are here: they do not mention zeroMQ nor jzmq:
http://storm.incubator.apache.org/documentation/Setting-up-a-Storm-cluster.html
According to the release notes of Storm 0.9.0, we now have the choice between Netty and ZeroMQ for tuple transport, so in theory you should be able to solve this issue by upgrading to 0.9.0.1, not install zeroMQ nor jzmq and configure storm as mentioned here:
(dawn, not allowed to post a 3rd link, ok, the release notes are on the Storm blog, in the Storm incubator apache web site ^__^)
-- Svend