I finally got everything to work - in case this helps anyone else:
httpClient.getParams().setParameter("http.socket.timeout",
new Integer(90000)); // 90 second
httpClient.getParams().setParameter(CoreProtocolPNames.PROTOCOL_VERSION,
HttpVersion.HTTP_1_0);
httpClient.getParams().setParameter(CoreProtocolPNames.HTTP_CONTENT_CHARSET,
"UTF-8");
post = new HttpPost(new URI(url));
Charset chars = Charset.forName("UTF-8");
StringBody user_id = new StringBody("32432", chars);
MultipartEntity multipartContent = new MultipartEntity(HttpMultipartMode.BROWSER_COMPATIBLE);
multipartContent.addPart("media_entry[media]", new FileBody(file));
multipartContent.addPart("media_entry[user_id]", user_id);
post.setEntity(multipartContent);
HttpResponse response = httpClient.execute(post);
response.getEntity().getContent().close();
does the trick.
The important part is the forcing of the HTTP/1.0 protocol, since most rails web servers don't support chunked-encoding.