Same Problem (on Sprint)....
Siri is working just fine, but dictation is not working. This is on a 32GB iPhone 4S. It very well must be a server issue, as we are seeing that certain servers must be handling the load of Siri, and other servers are handling the load of speech dictation.
Initially thought it was the Things application on iPhone (since I got that yesterday when I started having the problem), but found that the syncing via wifi with that app is not the problem.
Apple HAS to fix this, or else they will be in a mountain of trouble with the millions of users that got this phone for the specific reason of Siri speech dictation, among other things. For crying out loud, they advertise this as a major feature of the phone.... The hope is that it will be fixed very, very soon.
Good that I'm not the only one!