I also tried the following on a test string:

 s.encode("UTF-8", :invalid => :replace, :undef =>:replace, :replace
=> "?")

But it doesn't seem to replace the invalid character(s), the very
one(s) it's complaining about!

So I'm stuck because I'm getting the "invalid byte sequence" error,
yet the above function won't replace the invalid bytes.

TFM says:

":invalid : If the value is :replace, encode replaces invalid byte
sequences in str with the replacement character"

That's exactly what I'm trying to do but it isn't working. It isn't
replacing the invalid byte sequence it's complaining about with the
replacement character.