in reply to How do I include plus signs in POST LWP request
Try URL encoding your strings before sending them with HTML::Entities or similar.
Update Doh! Corion has suggested URI::Escape over HTML::Entities.