+1 on "UX starting at day 0".
[Minor caveat that I'm a dev and not a UX person so I might have a bit of a naive understanding of what is done/needs to be done from a UX perspective].
I have worked on Agile teams where UX folks were an integral part of the team and a few things that seemed to work well:
Early UX involvement
Often our interaction designer would "peek" up the backlog one or more sprints (based on current velocity) and start thinking about what the UX should be like
Early UX/Dev/Product Owner conversations about upcoming "stories"
This was done (we used Scrum) during backlog grooming sessions. The entire team would look into the backlog at least a sprint ahead; PO and/or UX would help describe the story; UX would maybe have some wireframes of the UI and walk the team through the interactions
Early Usability Testing
If at all possible start testing as early, ahead of the current sprint. Yes, this means you won't be testing on a functioning application. Try to create low-fi clickable wireframes or mockups. I've worked with interaction designers that have used html to wire up stripped down UI that has enough of the key interactions that they can at least get an initial sense of usability. Maybe try a tool like Balsamiq. I've even seen people do testing on paper ("where would you expect to x?").
Estimate alternatives
As part of this "grooming" process, the dev team is responsible for estimating or sizing what is being described. Often UX would propose multiple alternatives and dev would estimate each option. There is nothing that will make a PO less likely to negotiate than the feeling that they have no options.
Estimate cost of deferral
This can be a useful approach when trying to convince a PO to move a deferred UX-related story up the priority. Engage the dev team to estimate the cost of deferral. Things are often more expensive to re-do later down the road than they are to face them up front. Try to estimate the cost of doing something now vs doing it later. This is the card you play if the PO says, "we'll do it later. we need to focus on features now". Tell the PO how much more it will cost later, then the ball is in his/her court.
This is generally my strategy when working with POs, do your homework, present the options, and then trust that they will make the right choice.
I should add that facilitating collaboration in the team, if you're a Scrum team, is the job of the Scrum master - they should be actively looking for ways to help the team work better as a unit (including the PO).
So, the short version: early, early, early, estimate, estimate :p