At first I was convinced that Twitter did some sort of pingback to our url to do it's URL shortening bit, making all calls to http://localhost#key1=value1 invalid, but even if we used demo.testdomain.com, we had a 50/50 chance of success. Sip coffee, look at each other in frustration, rinse and repeat.
In a moment of desperation, I noticed that our demo server was adding a query parameter to our RESTful url, making it look something like http://demo.testdomain.com?lang=en_us#key1=value1, and for some odd reason Twitter liked it (for the record, our RESTful URLs use everything after the "#" symbol, so having a URL with "#" and no "?" was perfectly valid). In between fits of cursing at Twitter and some key pounding, we managed to insert a "%3F" (the url encoding for "?") in between our domain and our "#" symbol and VOILA!
For the record, I still have no idea why it would matter to Twitter whether or not we included the query string identifier, but it's most likely an issue with their regex expression. Lots of URLs have "#" to denote the anchor on the current page, so we're not quite sure why their URL shortener would throw up whenever it came across this format. BUT, if you are having issues with an invalid URL parameter on Twitter, you might want to throw a "%3F" in the URL parameter value between your domain and the "#" symbol.
The final url format before url encoding would look like this:
Hope this helps.