While GNU sed takes care not to munge NULL characters this is not the POSIX standard, therefore it's no surprise some implementations don't manage to edit binary files properly (not to mention that many implementations will struggle with long lines). Hence the search for a binary sed:

bbe is just that. It allows you to do operations on blocks --you can define the block size in a variety of flexible ways-- as well as on bytes. So the most simple substitution command from sed just looks exactly the same. It's gorgeous.

It is a C program that you'll need to compile, but has no build dependencies so you can use it pretty much anywhere.