A directory with a minimal testcase illustrating the bug.
Unzip and modify build.xml: adapt the arguments of the java "runserver" task to point to a server and existing repository the content of which can be deleted.
"ant runlocal": this will show that all literals are correctly stored, found and removed.
"ant runserver": this will show that the literal added from the program has its trailing newline stripped and that it is impossible to remove a literal with a trialing newline from the repository.
This seems to be an issue with either the RDF parser or writer used to (de)serialize the result, as it does not occur when using a local repository. I have ran a few tests and at first glance it seems specific to the RDF/XML parser, which is odd, because that format should (by default) not be used when communicating between client and server.
Issue seems to be caused by the underlying SAX parser that is used both by the Rio RDF/XML parser and by the transaction XML format reader/writer. The latter is what causes the problem observed by Johann. I haven't quite figured out _why_ but it seems it automatically removes a (trailing) newline.
Updated this to a problem specific to the Transactional XML parser (the fact that the RDF/XML parser also trims newlines is not actually a bug, AFAICT).
The problem occurs because the SimpleSAXParser used by the Transactional XML parser trims whitespaces (which includes newlines) when receiving a transaction document from the client.
Issue in TransactionReader (and therefore specific issue in handling of Repositoryconnection.add and remove over HTTP) is fixed. Created a followup issue for a similar problem in the RDF/XML parser/writer (which does not directly affect the HTTPRepositoryConnection, so is not as urgent).