Hello Narnie and fellow Linux user.
I too have a collection of .m4b files (mine from jw.org) I have been unable to get m4b files to work on the Fuze+ directly.
However, I was able to strip out the AAC audio stream from the m4b using ffmpeg using the -acodec copy switch
Fuze is happy with .aac extension but not .m4b. So I lose the chapter marks and png artwork, but it is still aac. And the conversion is quick as there is no resampling.
Maybe that would work for your situation.