There is nothing wrong with rebasing a feature branch imho. Feature branches should be considered ephemeral. But it probably depends on your team and project size.
My personal opinion is that it breaks history and CI tests for all the feature branches. But at GitLab we encountered customers that insisted on having a linear history after migrating from SVN. Therefore there is a function in the UI of GitLab EE to rebase a merge request when accepting the merge request. See http://doc.gitlab.com/ee/workflow/rebase_before_merge.html
The results from previous CI runs are no longer connected to the rebased commits, and most people don't have CI set up to retest each commit individually after a rebase.
I've never found this to be an actual problem in practice.
Indeed you need to do them again. But you also have to rerun them after a merge anyway. The problem is that you can no longer see which commits that you merged where green before the merge. For example is very useful if the merge itself breaks the tests (uncommon but it can happen).