Hi LadyL,
As you are mentioning … the odds are very high that this is a pillow issue (and a sleeping position issue would be the second highest possibility).
When you have a new mattress, the gap between your head and neck and your mattress changes because you will be sinking into the mattress differently and this often indicates the need for a new pillow as well. I can take some trial and error though to find the pillow that provides you a combination of your needs (good head and neck alignment in all your sleeping positions) and also your preferences. Subjective preferences play a much more important role with a pillow than with a mattress because the pillow is so close to our face which is very sensitive to preferences of “feel”.
The pillow thread here may also be helpful
Phoenix