A colleague's CV is taking credit for service that I did, and now we're both on the shortlist for a job. Is there anything that I can do?
I would just ignore it.  I doubt that anyone will even notice unless they look at the two CVs side-by-side, and even then, they will probably just assume that the two of you worked on the redesign together.  They wouldn't doubt your honesty (nor the other editor's).  So I don't think this really disadvantages you.  

It might be a slight unfair advantage for the other editor, but I think it's minuscule.  In hiring decisions, things like professional service get a very low weight.  The fact that you were an editor is perhaps somewhat helpful, if the journal is recognized as publishing good research, but what you actually did as editor is too minor a point.  The fact that you can redesign a journal may speak to your graphic design skills, but academic jobs don't care about that - they care about your research and teaching (in some combination).  In fact, I'm not sure it is wise to emphasize it in application materials or interviews - people might think that tinkering with your journal could be a distraction from actually doing research.

If the topic of the redesign comes up at the interview, just describe honestly what you did.  You don't need to get into what your co-editor did or didn't do.

I doubt that you will be asked specifically about the fact that both of you are claiming credit (for one thing, it would reveal that the other editor is also a candidate for the job, which would normally not be shared with other candidates).  But if so, I would say something like "As co-editors, we share the responsibility for what happens to the journal on our watch.  But on this particular project, I took the lead."