I can post the SOAP because it's not being logged by NetSuite, this error is happening upstream from the point it's logged.
I noticed this error happening Friday, so this may be related to a Thursday night update.
The problem seems to be that if I include a date filter in a CustomRecordSearchBasic then I will get this "missing date parameter" error. I have confirmed the date being supplied is valid and as I mentioned already this worked Thursday.
Is anyone else experiencing a similar problem?