I cannot add parameters to external data connection (SQL query) in Excel
2007.
I am trying to add an external data connection in Excel 2007. I create a new
connection to my SQL Server. I change the properties to a SQL statement. I
embed a question mark (?) where I need parameters, but the "Parameters"
button remains grayed out and unavailable. The query fails with a "No value
given for one or more parameters." Error.

This applies to queries against a stored procedure or table function.

Frustratingly, I have been occasionally successful in getting the Parameters
button available. When I set up the parameters, the query works fine. But I
cannot reproduce this behavior 90% of the time! Even within the same
spreadsheet against the same data source.

What do I need to do to make the parameters button available for queries
with parameters?

After running into the same problem, I discovered that the (?) parameter only applies when using MS Query to setup the Data Source (Data / Get External Data / From Other Sources / From Microsoft Query).
You will see that the Connection Properties / Definition tab shows the connection type as a 'Database Query' vs. an 'OLE DB Query'. From here parameters may be added merrily by using a new ? in the command text.