Here is the scenario. Story was completed as written and scheduled for the next release. We found out a day later that there were other systems that needed to do changes as well and would not be ready in time for the next release. Keeping this story on our board looks like we have code going into the release when in fact this needs to be pulled out. Creating a new story to remove code for the other story seems like a very confusing scenario for someone who is not familiar with our board.
TL;DR: If it happens within a Sprint (as in your case), move the Story back to To-Do. If that happens after Sprint end, a new Story is needed.
Exploring the situation in details:
Story was completed as written and scheduled for the next release.
A Story is completed when the definition of done is completed. Thus, if by the time the story was completed the DoD was met and the story was accepted, it's now shippable software. So far, so good.
We found out a day later that there were other systems that needed to do changes
This is an external dependency problem. Ideally, no work should enter into the Sprint if it has dependencies to external factors (or at least, they should have been clarified and agreed beforehand). A good reminder for the day the Agile manifesto celebrates its 20th anniversary: "Simplicity--the art of maximizing the amount of work not done--is essential".
Keeping this story on our board looks like we have code going into the release when in fact this needs to be pulled out. Creating a new story to remove code for the other story seems like a very confusing scenario for someone who is not familiar with our board.
Here, a more important aspect than this single Story itself comes to play: The Sprint goal. If the Story was "Blow 20 candles" and the goal was "celebrate the agile manifesto anniversary", you can do whatever you want with the Story that you still won't be able to fully accomplish the goal, so you'll need to hold your breath for the next Sprint...
Let's look at the options you mentioned:
- Have another Story for the next Sprint to roll back the code. After all, you have delivered what you had planned for the Sprint. As you mentioned, it'll look like you're going into the release when you shouldn't. This is gaming the system, putting outputs over outcomes. Not recommended.
- Create another Story to roll back code. As you said, it's a bit messy too, specially if you have some sort of relationship between the Story and the actual code (*ahem* Jira *ahem*). Besides, you'd be adding a new Story into the Sprint that will add low to no value. Not recommended.
- Reopen the Story and move it back to "to do" with a big red note "wait for those slackers over there". This may be really unpleasant, but that's reality. The Story isn't done. Next time, double check there's no external dependencies before prioritising something into the Sprint backlog. And for now, roll back the code.
Some may not like to not be able to accomplish the work planned. Some may prefer outputs over outcomes. I'd say entering into these discussions only waste everyone's time. Plan better and review with the broader group how to reduce cross team dependencies. That's by far a better investment of energy and attention.
I think that you should "park" that story – it's not ready to go yet – and create new ones which specify the other changes that need to take place (first ...) in the various other systems.
And, to me, "this is not necessarily a fault in the existing 'story.'" You completed the work, but you shouldn't merge this change-control branch into the next release. More "stories" are needed. Perfectly understandable ... glad you folks caught it in time.
There is no set approach to this situation, but it looks like you already have the right focus:
Creating a new story to remove code for the other story seems like a very confusing scenario for someone who is not familiar with our board.
Do what ever you think will best help the people that consume your board to understand what is going on. It may even be worth having a conversation with your stakeholders and ask them what their expectations would be in this kind of situation.