I already brought this up with Vim's developers with all the relevant details in the mailing list discussion here: https://groups.google.com/forum/#!topic/vim_dev/tZPJ7mx2FQg The issue at hand isn't entirely their fault and is the result of Vim not having been packaged properly on Fedora's end. Possible solutions from the packaging perspective might include not compressing the help files as is currently done in the package, modifying vimtutor to load the gzip plugin if necessary, or perhaps encouraging the Vim developers to implement the changes that I proposed in the mailing list discussion.
Actually vim-minimal didn't handle compressed documentation properly either. I'll revert that compression in the next vim version
vim-7.4.1868-1.fc23 has been submitted as an update to Fedora 23. https://bodhi.fedoraproject.org/updates/FEDORA-2016-28873e4832
vim-7.4.1868-1.fc24 has been submitted as an update to Fedora 24. https://bodhi.fedoraproject.org/updates/FEDORA-2016-3a7f36c0c1
vim-7.4.1868-1.fc22 has been submitted as an update to Fedora 22. https://bodhi.fedoraproject.org/updates/FEDORA-2016-2cdb5d5a7c
vim-7.4.1868-1.fc24 has been pushed to the Fedora 24 testing repository. If problems still persist, please make note of it in this bug report. See https://fedoraproject.org/wiki/QA:Updates_Testing for instructions on how to install test updates. You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2016-3a7f36c0c1
vim-7.4.1868-1.fc23 has been pushed to the Fedora 23 testing repository. If problems still persist, please make note of it in this bug report. See https://fedoraproject.org/wiki/QA:Updates_Testing for instructions on how to install test updates. You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2016-28873e4832
vim-7.4.1868-1.fc22 has been pushed to the Fedora 22 testing repository. If problems still persist, please make note of it in this bug report. See https://fedoraproject.org/wiki/QA:Updates_Testing for instructions on how to install test updates. You can provide feedback for this update here: https://bodhi.fedoraproject.org/updates/FEDORA-2016-2cdb5d5a7c
vim-7.4.1868-1.fc23 has been pushed to the Fedora 23 stable repository. If problems still persist, please make note of it in this bug report.
vim-7.4.1868-1.fc24 has been pushed to the Fedora 24 stable repository. If problems still persist, please make note of it in this bug report.
Can confirm this is fixed in Fedora 24 -- thanks! :helpgrep works again.
vim-7.4.1868-1.fc22 has been pushed to the Fedora 22 stable repository. If problems still persist, please make note of it in this bug report.
Fedora 22 changed to end-of-life (EOL) status on 2016-07-19. Fedora 22 is no longer maintained, which means that it will not receive any further security or bug fix updates. As a result we are closing this bug. If you can reproduce this bug against a currently maintained version of Fedora please feel free to reopen this bug against that version. If you are unable to reopen this bug, please file a new report against the current release. If you experience problems, please add a comment to this bug. Thank you for reporting this bug and we are sorry it could not be fixed.