I am getting a message Protocol error in TDS Datastream from a SQL Server query.

A. Three things may be happening :-

1. SQL Server is internally gpf'ing/AV'ing (same thing) - you should see messages to this effect in the SQL errorlog. 
2. Net-lib bug with overlapped/fragmented packets.
3. A complex query is generating incorrect TDS syntax in the packets

For all problems you can try applying the latest SP to the server. You should also search the knowledgebase at http://support.microsoft.com 

For net-lib bugs you will need to apply to the client as well. Also the version of ADO/ODBC can help cause the problem as well, so try upgrading. The latest versions of these drivers can be downloaded from www.microsoft.com/data.

If you're getting access violation messages, then see the FAQ entry on access violations in the FAQ.

If it is being caused by a complex query, then try re-writing the query - breaking it up into smaller chunks. If this is not possible, see if the problem occurs when you run the query via ISQL/W instead of via the application.

If you are getting a problem with TDS packet fragmentation (TDS is SQL's application level protocol) then try a different net-lib - e.g. tcp-ip instead of named-pipes or vice-versa. If still no-go then you'll need to call Microsoft PSS.

Even if a different net-lib fixed the problem, then please still report the problem to Microsoft PSS. Unless Microsoft get these bug reports then they can't fix them. (With a repro script an MVP will do it for you). Your call fee WILL be re-imbursed as all calls about bugs are free. (However, on the "normal" support-line the person answering the phone can't know it's a bug, so they'll need your credit card details anyway).

Microsoft will need you to supply :-

SQL Errorlog(s)
NT event log(s) - if any NT errors were occuring at the time
TSQL code running at the time
Details of hardware, version of NT, servicepacks etc. WINMSDP output is good for this.
A SQL Trace of what happens at the time of the error
Possibly a network trace between client and server as well

With SQL 7 there is a new utility that will garner most of this information for you automatically. It is called sqldiag - 
sqldiag -U -P -O