Sounds to me like there is air in the pick-up tube and the pump is struggling to fill it with oil.
Did you pre-lube the new oild filter when you did the change?
You might want to pull the filter and see if its filling.