What is the security loss from reducing Rijndael to 128 bits block size from 256 bits?
Security issues related to block size boil down to the following: a pseudorandom permutation is not a pseudorandom function, and the difference becomes visible when you query the function too many times. Imagine a function which accepts as inputs, and offers as outputs, elements from a set of size $N$. For instance, the inputs and outputs are blocks of $n$ bits, so $N = 2^n$. If you feed this function with different input values, then you will first get as many different output values. However, with a PRF, you expect to obtain a collision at some point: a new input which yields the same output as a previous distinct input. On average, this should occur after about $\sqrt{N}$ queries. With a PRP, you will never get a collision, because permutations are, by definition, injective.

So when encrypting with a block cipher, using blocks of $n$ bits, you begin to have problems when processing more than $2^{n/2}$ blocks with the same key. 3DES has 64-bit blocks, so encrypting more than $2^{32}$ 8-byte blocks with 3DES can be troublesome: that's 34 gigabytes or so, a value which is not so huge nowadays. To avoid this problem, NIST launched an open competition for an "Advanced Encryption Standard" (the AES) with the following rules:


128-bit blocks.
Keys of 128, 192 and 256 bits.
Not slower than 3DES (many candidates turned out to be widely faster).


And that's what they defined. They did not really care that the selected candidate (Rijndael) had extended versions which could accept other block sizes; 128 bits were sufficient.

In all of the above, the important point is that the $2^{n/2}$ figure is related to the number of queries. It is generally estimated that, for an attacker, obtaining $x$ pairs plaintext/ciphertext is widely more difficult than trying out $x$ potential keys, since the former requires cooperation of the target system, while the latter requires only some computing power on the attacker's own machines. You'll have a hard time finding an "honest system" which needs to encrypt $2^{68}$ bytes with AES (that's close to 300 billions of gigabytes), and even more so an honest system where the attacker can get 300 billions of gigabytes of known plaintext while still being "locked out" (if the attacker can get the honest system to process that much data, then what left is there to attack ?).

Basically, the block size and the key size work on different scales, and it just happens, fortuitously, that "128 bits" is a nice level for keys (exhaustive search on $2^{128}$ keys is not feasible with current technology), and also a nice level for block size ($2^{64}$ blocks of 16 bytes of known plaintext is not a realistic attack scenario with current technology).

Notably, if a quantum computer ever sees the light, that computer would be able to break a 128-bit key in $2^{64}$ effort, but it would do absolutely nothing about the issues related to block size: 128-bit blocks would still be as good as they are today.



All of the above is for usage of a block cipher for encryption. When a block cipher is to be reused as a core element for something else, e.g. a hash function, then other constraints may apply. Typically, for the Skein hash function, the internal block cipher had to offer much larger blocks if the hash function was to live up to its promises (note that a hash function has no key, so we are far from the attack model of an encryption system). This is why Threefish, the block cipher in Skein, has big blocks. This is not because big blocks are good for encryption; this is because big blocks are necessary when a block cipher is turned into a hash function the way Skein does it.

A similar case is Whirlpool, which uses the "W" block cipher, which is a Rijndael derivative (with even larger blocks -- 512 bits -- and a revamped key schedule).



As for D-Wave systems, they are not "true" quantum computers; they compute a specific problem instance in a "somewhat quantumish way", but are not able to apply the nifty algorithms which eat crypto for breakfast. The difference is qualitative, not a question of mere tuning. See this for pointers.