Rally requires ISO8601-formatted Dates, so a query string of the format:
string queryString = "(LastUpdateDate < \"2013-04-15\")";
Should work for you.
Just a heads-up, especially if you're just getting started with building your integration, I'd highly recommend using one of Rally's .NET REST SDK instead of SOAP.
REST is more robust, more performant, and, Webservices API 1.4x (x is yet-to-be-determined) will be the final API release to have SOAP support. Webservices 2.x will be REST-only, so using REST will be essential to anyone wanting new Webservices features moving forward.