I have a different phone, but I had the same problem on mine with a 4.3 AOSP rom. The trick was to install both Voice Search and Google Search apps together. My rom said voice search was already installed so I had to manually delete the apk files first with a root file manager before the Play Store would let me reinstall it.
YES! YES! After the last update to Android version 4.3 (which included an update of the keyboard) on this Google Nexus 7 (Jellybean OS) the Mic icon/key was replaced by a Settings icon/key. The way it was setup before, you held the Mic Key to access the Settings Key (which was awesome!). Just like you I'm SO disappointed they took the Mic! I used it a LOT. Especially nice for dictating emails, which I have to type now :-( I contacted Asus, they suggested I wait till the next update to see if the Mic comes back.....but "I WANT IT NOW!!" lol. PLEASE post anything you discover regarding Mic recovery.
![]()