A block cipher is a key-indexed pseudo-random permutation on the space of blocks: for a given key K, AES maps 128-bit blocks to 128-bit blocks, such that no two distinct input block values are mapped to the same output block value. Knowledge of K allows efficient computation of the inverse permutation as well.
A block cipher can be used as a building element for various process, including (but not limited to):
- symmetric encryption of arbitrary long messages, using various mode of operation;
- hash functions, e.g. with Merkle–Damgård or some other constructions;
- MAC algorithms, with (for instance) CBC-MAC;
- generation of unique, pseudo-random, verifiable identifiers (my encrypting successive values of a counter in a given range).
A stream cipher is a specialized algorithm which covers only the "symmetric encryption of arbitrarily long messages" use case. The hope is that by restricting ourselves to that single usage, we may design a more efficient algorithm. The eSTREAM competition resulted in a portfolio of seemingly secure stream ciphers which indeed happen to be faster than AES-based encryption on a number of architectures (e.g. on a 2.4 GHz Core2 x86 CPU, I can do AES at 160 MBytes/s, while the Sosemanuk stream cipher reaches 700 MBytes/s on the same hardware).
Note, though, that "symmetric encryption only" is restrictive: in many situations where symmetric encryption is desirable, one should also add integrity checks, i.e. some sort of MAC. Stream ciphers don't do MAC, while there are authenticated encryption modes which allow to turn a block cipher into both encryption and a MAC, with relatively little overhead when compared to raw encryption (by the way, there is an ongoing competition for new AE modes, which received no less than 57 submissions, so we should have in the future some even better AE modes).
It has also been pointed out that there are encryption contexts where random access is desirable (e.g. hard disk encryption), and you get that with a block cipher in CTR mode, but not necessarily with a dedicated stream cipher.
To sum up, you should consider using a stream cipher in a new protocol only if you have a performance issue to solve, and the problem at hand happens to be within the limited scope of stream ciphers. This does not happen often. An example is when you need gigabytes of pseudo-random bytes (basically, when I need random bytes in huge quantities, I use Sosemanuk initialized with a key and IV from /dev/urandom).
