I don't think its a wifi issue Simon, because if I use voice search it responds immediately, but I assume the "OK Google" wakes it from its reveries and off we go. It seems that it does not fully respond to typed commands.
Its very strange and it is such an odd occurrence I really can't get any info on the web about it.
I've tried disabling the AV but that didn't help. It is only on the Samsung Tablet, it works as normal on my Samsung phone so its probably not the TouchWiz interface either...