I tested Android 39.0.1 Candidate Build 2 on both my Nexus 5 & Nexus 7, both running Android 5.1.1. Builds are from http://ftp.mozilla.org/pub/mozilla.org/mobile/candidates/39.0.1-candidates/build2/android-api-11/en-US/fennec-39.0.1.en-US.android-arm.apk After installation (update from 39.0), the search widget was no longer functional and available in the Widget Set.
Sorry about that, this is due to bug 1180995. We don't plan to ship this build to users on the play store, and the widget functionality should be back in place by the time we do ship our next update.
Something like that. This is my reminder to back the bad patch out.