Why should I use Authenticated Encryption instead of just encryption? There are various different modes of operation for block cipher use, some of which provide "encryption" and some of which provide authenticated encryption.

Why should I use an authenticated encryption mode rather than just an encryption mode?

This question does not aim to discuss different modes of authenticated encryption vrs encryption modes (although a good answer might choose to): its aim is to justify why/when AE is better than 'plain' encryption.
The crucial difference between plain encryption and authenticated encryption (AE) is that AE additionally provides authenticity, while plain encryption provides only confidentiality. Let's investigate in detail these two notions.
In the further text, we assume $K$ to be a secret key, which is known to authorized parties, but unknown to attackers.
Goals
Confidentiality (privacy) means that an attacker can not get any information about the plaintext $P$ from the ciphertext $E_K(P)$ except, possibly, for the length. In other words, the ciphertext looks like a random string for those who does not know $K$, even if they have some control over the plaintext. All the folklore encryption methods, from one-time pad to Enigma, provide confidentiality (under some assumptions) and only it.
Data authenticity (integrity) means that an authorized party (receiver), who possesses $K$, can check if the received data $D$ is genuine, i.e. it has been constructed only by a sender who knows $K$. The data can be cleartext or ciphertext, and there is a subtle difference what is authentic in each case: if the ciphertext is authenticated, then we know that the key owner authorized the ciphertext, but not necessarily plaintext. A traditional way to achieve authenticity is to use Message Authentication Code (MAC):
$$
H_K(D) = T,
$$
where $T$ is called tag.
In the world of public-key cryptography, the same goal is achieved with digital signatures.
What you need
A user is usually able to decide which of these properties he is looking for. For instance, if he knows that an attacker can not modify data, he may not need to authenticate it. However, if he needs both, there are secure as well as insecure ways to combine the schemes of two types. For example, a naive approach to use the same key $K$ in both schemes is dangerously insecure for most instantiations. Hence a combined scheme is recommended.
Authenticated encryption
Authenticated encryption (AE) provides confidentiality and data authenticity simultaneously. An AE scheme is usually more complicated than confidentiality-only or authenticity-only schemes. However, it is easier to use, because it usually needs only a single key, and is more robust, because there is less freedom for the user to do something wrong (see also a more elaborative answer).
As a separate feature, an authenticated encryption scheme may authenticate, but not encrypt, a part of its input, which is called associated data. For example, we may wish to encrypt the contents of an Internet packet, but we have to leave its header unencrypted but still bound to the internal data.
Security
We have not specified yet what we mean by a secure scheme. Apparently, there are several security notions, and the user has to choose among them according to the capabilities he expects from an adversary.
For confidentiality-only modes of operation the most popular security notion deals with chosen-plaintext attacks. Let $E$ be an encryption scheme. We assume that the adversary not only knows some plaintexts $P$, but is also able to choose some of them for the encryption (this is quite a practical situation). Hence, we allow the adversary to choose any plaintext for the encryption, and many times in a row. What we still require from a secure scheme is that it outputs randomly looking ciphertexts in each case:
$$
E_K(P_1),E_K(P_2),\ldots, E_K(P_n) \sim RandomString(|P_1|+|P_2|+\cdots+|P_n|)
$$
The adversary can not distinguish the whole set of ciphertexts he obtains from an output of true random bit generator of the same length, even if the adversary repeats his plaintexts. The latter requirement implies that the scheme must be non-deterministic, and indeed, the confidentiality-only modes that satisfy these requirements are either probabilistic or nonce-based.
I note that there are folklore security notions that relate the security of the scheme with the ability to recover the key $K$ itself. This was relevant when the key could be used elsewhere, but this is far less common now, and the security notion described above is prevalent.
The security of authenticity modes is defined in a different way. Let $H_K$ be such scheme with the secret key $K$. We require that if the adversary chooses any data $D$ that has not been authenticated yet, then his chances to guess tag $T$ such that
$$
H_K(D) = T
$$
are negligible. If he submits the pair $(D,T)$ to a verifier, he will get the answer $\perp$ (error).
Note that we have not talked about chosen-ciphertext attacks on confidentiality-only modes. These are attacks when the adversary is also able to send his own ciphertexts for decryption. While this setting also appears in practice (even though less often than chosen-plaintext attacks), the confidentiality-only schemes can not resist such attacks. To establish this sort of security, the user must turn again to the authenticated encryption.
Security of authenticated encryption schemes is defined in two parts. First, similarly to confidentiality-only modes, the adversary must be unable to distinguish the ciphertexts from random strings. Secondly, whatever fake (not created on $K$) ciphertext she sends for decryption, she is likely to get $\perp$ in response.
Therefore, the authenticated encryption modes provides you also security against chosen-ciphertext attacks if it is needed.
How it works
There are numerous integrated authenticated encryption schemes: CCM, GCM, OCB, EAX, etc, where mechanisms that establish confidentiality and authenticity are tightly coupled. The design of these schemes is far beyond the topic. However, there is a simple composed scheme, well-known as Encrypt-then-MAC, that works as follows. Let $K_1,K_2$ be secret keys, $P$ be the plaintext, $E$ be some encryption mode, and $H$ be some MAC. Then the scheme
$$
\Pi_{K_1,K_2}: M\rightarrow E_{K_1}(M) ||  H_{K_2}(E_{K_1}(M))
$$
is a secure authenticated encryption scheme if $E$ is a secure confidentiality mode and $H$ is a secure authenticity mode.
Additional features of authenticated encryption schemes
Besides providing both confidentiality and authenticity, authenticated encryption schemes may have a number of additional features. No scheme has them all, hence the best choice is determined by user's settings.

Security level. A scheme guarantees confidentiality and data authenticity only up to some bound on the amount of encrypted data or decryption requests. This bound is typically much lower than the key space, and for AES-based modes does not usually exceed $2^{64}$.

Parallelism If a lot of resources are available, one may desire to run the encryption, decryption, or verification in parallel. The modes that use  chaining (like the ones derived from the CBC encryption or the sponge construction) are difficult to parallelize.

Online encryption. We say that a scheme is online, if it allows to encrypt immediately when the data is available, without the knowledge of its length.

Use of patents. One of the most interesting AE schemes, the OCB mode, is patented, and is less frequently used and analyzed because of this property. It is often desirable that the scheme is patent-free.

Tag update. Most of the schemes, with a few exceptions like GCM, require to recompute almost entire ciphertext if a small portion of plaintext is modified. If the ciphertext can be updated quickly, it would allow much faster processing of large amounts of encrypted data, e.g., hard-drive encryption.

Use of nonces or random IVs. Nonces and random IVs lead to distinct security models, which are often incompatible (schemes might be secure with nonces, but not with random IVs of the same length, or vice versa). While the nonce uniqueness might be harder to ensure, the random IVs need a separate random-number generation mechanism and leads to the ciphertext expansion.

Variable key, nonce, or tag length. All the three parameters are usually restricted by the application that uses an AE scheme. In turn, AE schemes  have their own, sometimes incompatible restrictions. The more variability the scheme has, the more applications it suits.

Processing of associated data. All the modern schemes allow for the authentication of associated data, which is not encrypted. Some of them, however, can not preprocess AD before the plaintext is over, which might be a penalty on the performance.


Additional reading
The technical report by Rogaway is a comprehensive survey of confidentiality-only modes, MACs, and some authenticated-encryption modes. It also contains all formal details about security notions.