Does it take brute force to find a pair of plaintext and ciphertext that each follow a certain condition, given an AES encryption key? Suppose that I have an AES key $K$, and I'm instructed to find a plaintext such that the first 32 bits of the plaintext are some string of bits $S_1$, and the last 32 bits of the ciphertext once the plaintext has been encrypted with $K$ are another string of bits $S_2$.

Is this difficult? Is there a known attack against this that's faster than just fixing one of the $S$'s and brute-force searching for a text with the other $S$?
Well, it's moderately difficult; you couldn't use that as a security assumption; however, it would be too difficult to expect someone to solve during an active protocol.  There's no nonobvious trick to it; the two methods at your disposal would be:


Select random plaintexts with the first 32 bits as $S_1$; encrypt them with key $K$, and check to see if the last 32 bits of the ciphertext happen to be $S_2$
Select random ciphertexts with the last 32 bits as $S_2$; decrypt them with key $K$, and check to see if the first 32 bits of the plaintext happen to be $S_1$


Either approach will take an expected $2^{32}$ random trials before success; at 1 $\mu$sec per AES operation (quite conservative; modern CPUs typically can do several times as fast as that), we're looking at perhaps an hour or two.

Perhaps you were hoping there was some clever way to take advantage of the partly known plaintext/ciphertext; it doesn't work out.  For example, you might be hoping to translate the AES cipher into a large series of boolean operations (with the known key, and known 32 bits of plaintext and ciphertexts), and solve the resulting set of equations.  However, AES has a fairly quick 'avalanche'; very quickly (within two rounds), all the internal bits will depend on all the unknown bits in subtle ways; the resulting set of equations will not have an easier solution than just trying various combinations of the 96 bits on one side (which is effectively what the straight-forward solutions do)