I know your question was initially about sed, but there is a beautifully simple answer in vim:
:g/.\npattern/norm o
Or, if you would rather run this entirely from the command line:
vim file -c "g/.\npattern/norm o" -c "wq"
The way it works, is that it looks for any line that matches the following regex:
.\npattern
which is any non-empty line followed by your pattern. Then, for each match, it applies the following command norm o, which opens up a newline below the current cursor location.
This should work for vi also.