Ok, I've sorted it.
Mistake number 1:
ldi loads an immediate value, e.g. a constant. No good for passing in values which change.
Mistake number 2:
Specifying "M" in the input parameter binding, again, it's for use with constants.
What I should have been doing is using the mov instruction, and passing in using the "r" option, so that the value goes into a register.
So, the fixed code:
void setup() {}
void loop() {
byte thebyte = 128; //This works as intended, right up to 255
asm volatile (
"mov r16,%0" "\n\t"
::"r" (thebyte)
);
}
Oh and thanks Mark for having a go, and not saying "you shouldn't be using assembler" 