I think I once faced the recommendation, that the initialization vector should always be random and never be used twice with the same key.
How serious is this weakness?
Also, is AES less effected than DES?
The initialization vector is a property of the mode of operation (aka "chaining mode"), not of the block cipher itself. A block cipher does only one thing, which is mapping blocks (block size depends on the cipher, 64-bit for DES, 128-bit for AES) unto other blocks. The chaining mode is what says how input data should be transformed into block values, and how the corresponding encrypted blocks should be combined.
The simplest chaining mode is ECB, in which data is split into blocks in the natural way. The main problem is that for a given key, the block cipher will always transform the same input block value into the same output block value (the algorithm is deterministic), which means that with ECB, the encrypted message will show identical block values where the input blocks were identical. The Wikipedia page linked to above has a nice picture which illustrates what's wrong when applying ECB to a picture. In a general way, this is because "real-life" data has redundancy.
CBC corrects the problem by "randomizing" the input blocks by XORing each input block with the previous encrypted block: encrypted blocks have a "random look" (if the block cipher is any good) so this makes the occurrence of two identical blocks improbable. The IV is just the "previous encrypted block" for the first data block.
CBC is secure as long as the P xor C values, where P is a plaintext block and C the previous encrypted block (or the IV), do not collide more often (or less often) than randomly chosen value would. Since real-life input data has structure, this implies that this "random distribution" must come from the encrypted blocks. A good block cipher will ensure that, except for the IV which is not an encrypted block; so the IV must be randomly chosen. At the extreme case, if the IV is always the same for a given key, then two plaintext messages which begin with the same bytes will yield encrypted messages beginning with the same sequence of block values, and the attacker will see it. More generally speaking, if the IVs have some structure in their choice (e.g. a counter), then that structure could interact with that of the plaintext messages, and again yield collisions which reveal information on the encrypted messages. Conversely, if for a given key you encrypt only a single message, then you can use a conventional IV (e.g. an all-zero IV), because trouble begins when considering two messages encrypted with the same key.
All of the above equally applies to DES and AES. However, the 128-bit blocks of AES make it a bit less vulnerable to sloppy IV selection, because real-life data tends to show less redundancy at the 128-bit level than it does at the 64-bit level. This is still a weakness, and you shall use properly generated random IV for AES too.
Some recent mode of operation (e.g. EAX) have less stringent requirements on IV selection: EAX only needs unique IV values, but does not require random selection (a counter, incremented for each message, is fine with EAX).