Programming skills are more important for a physicist than is a knowledge of theoretical computer science, but because all the best programmers have this knowledge, you are in good shape.
I would have to say a C.S. degree would be very valuable to a computational physicist. I worked briefly with COSMOS (a hydrodynamics simulator) and the code base was quite large. Understanding how to plan and organize your code is necessary to efficiently manage such a project.