Google Search stalls on Android Tablet

[stevenrw]

I realise this is not a particularly active board but I'm hoping somebody can help.
I have a new Samsung Galaxy A 2016 10.1 tablet running Marshmallow. I have the Google search box widget on the home page but it behaves very strangely.
Voice search brings up results in the normal way, but if I type in a search term the blue status bar moves to about 90% across then stops. I have to hit the magnifying glass again and then it works.
This only happens the first time I use it after starting up. After that it seems to work fine.
Then I power down, and the next time I boot up and use the search box it does the same thing.
Any ideas?
I have cleared the Google App cache and deleted/reinstalled the widget but nothing seems to fix it. I can't seem to find any similar problem on any of the Android forums either.

[Simon]

Just a thought, but I have an HTC 10, also on Marshmallow, and the WiFi seems quite flakey when I first start up the phone.  I wonder if there's a WiFi issue with Marshmallow?  I don't use the Google search bar, but perhaps it's dropping it's connection, hence the shaky start? 

[stevenrw]

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...

[Glenn]

I presume the tablet has been powered off and the problem still exists? Factory reset?