I have seen and participated into this debate many times - what design we should tackle first, visual or interaction? There is no one answer, but here are some thoughts. What we really need is a good framework in place during the design phase before we work on the details of any of these designs. The actual design cannot be accomplished until we have idioms, metaphors (for interaction design) and brand, visual theme (for visual design) etc. flushed out and agreed upon.
One designer describes visual design as skinning the wireframes to prevent the end of wireframes and hence death of interaction design. This is a bit extreme and many visual designers won't be thrilled with this opinion. Wireframes are good tools to document interactions and to get a quick validation via cognitive walkthroughs. Visual design is horizontal and it should be made sure that it is consistent across all the parts of an application so that they have the same visual appeal. Interaction design is vertical and could describe some very specific interaction scenarios for each set of pages.
Users would however recognize the visual design appeal first and may not even have direct appreciation for good interaction design until they figure out they can accomplish everything in an application without putting in a lot of thoughts. The visual design is easy to demonstrate than to document it and that's why people jump to photoshop since transformation of visual artifacts from photoshop to actual web-based application is not that difficult. On the other hand interaction design deals with data, user's intents and actions, feedback etc. There is no one-one relationship from wireframes to the actual screens but having detailed wireframes help developers establish good understanding of the interaction model and designer's expectations. We highly encourage that designers co-locate with developers but if that's not the case, especially for remote teams, documenting design is critical.
I am not trying to downplay the role of visual design - it is the "look" part of look and feel and it's not just about the skinning of wireframes. Visual designs need their frameworks too such as CSS, typography, symmetry, balance, etc. but there are many ways to slice and dice time on interaction and visual design in a project - these are not the alternatives at the same level. I don't want to stereotype developers, but most of the developers think that the only design that they need is visual design and not the interaction design since the discipline of interaction design is less known in the developer community. Alan Cooper's work, especially "The inmates are running the asylum", describes this conflict in detail. Developers follow "system model" as described by Don Norman which is essentially an implementation centric design. Designers should make every possible effort to document and emphasize the interaction design to achieve overall user experience. The visual design is, well visual, and developers are more likely to embrace it or even ask for it.