Our team is pretty good at planning/pointing, but once in a blue moon, we will have a severely underpointed story. I'm talking something we thought it would take a couple days and we realize its going to take the whole sprint. What is the recommended approach to fix this when we realize our error so that it doesn't make our velocity unusable for the next sprint planning?
As soon as you identify a story that is too large to absorb in the current iteration your team needs to do the following ASAP:
Communicate your concern to the whole team. Since you tagged this scrum you need to talk to the Scrum Master and Product Owner specifically, but everyone needs to be aware.
Identify what it is that made it take more time. Odds are there was something missed during estimation. Either a missed requirement or something really was tougher than it looked (e.g. some feature cannot be implemented the way you assumed earlier due to a framework limitation).
Come up with a new estimate given the new information.
If it is too big for a single sprint or it makes sense to split it into multiple stories, break it up into multiple stories and move them to the backlog. If possible, move one of the new (smaller) stories back into the current sprint in the now-empty space.
Else if its new size is small enough for the current iteration, leave it in place (not likely in your case but a good step to leave in for the general case).
Else move it to the backlog.
Letting the story slip can look bad, but you know what is worse? Perpetual crunch-time and everything else that comes with procrastination and lack of planning.
Your actions should be determined by whether the decrease in velocity due to an underestimated story is a one-time or rare excursion, or a trend suggesting your development process needs refactoring.
You need better metrics to detect the difference. IMO, computing the average velocity over just the last two sprints is not sufficient. You should be collecting over all previous sprints to detect long term trends.
At the start of a project, the team's effort estimates will likely be in error from the actual effort. The velocity from sprint to sprint can be expected to show large fluctuations. As the team gets more familiar with the project tasks and better at estimation, there should be less fluctuation and the velocity should converge to a consistent sustainable value with smaller range of variation. In statistical terms, the standard deviation of velocity should start out a fairly large fraction of the velocity, but converge to a fairly small fraction of the velocity.
If your velocity is showing large fluctuations from sprint to sprint consistently, this suggests your estimation process needs improvement. There are many actions you might take, depending on the specifics of your program. Is it a matter of training the developers to do estimation better, is it a matter of better understanding of the problem domain, are there political issues making the estimation process unreliable? All of these and more are possibilities.
If this is not the case and your velocity has converged, but the underestimated story is a one time excursion: that doesn't make your overall moving averaged velocity unusable for the next sprint.
What it does do is make the estimate of your outlier story's relative contribution to the velocity too small.
You need to re-estimate the contribution of the outlier story to the velocity of the next sprint, scaling it up by a factor that takes into account the mis-estimate. Then you must make adjustments to the sprint to keep the velocity at your sustainable value.
This can mean pushing other stories to the backlog if the underestimated story has a higher priority or splitting the story into smaller stories to tackle over multiple sprints if other stories can't be pushed to the backlog.
What is the recommended approach to fix this when we realize our error
Estimates are estimates. I would not view it as something to be fixed, when it happens. I would view it as an opportunity to diagnose the reasons and improve your future estimates. Since the aim of Scrum is high quality increments of deliverable product, you want to stop and assess what is the best quality increment you are capable of delivering that Sprint, given that you now realize that you initially "bit off more than you could chew".
...so that it doesn't make our velocity unusable for the next sprint planning?
You don't need to be a slave to your method of calculating velocity. You could, for example, chose to consider the data from the current Sprint to be an "outlier", and not use it in your calculation (which I presume is some kind of rolling-average of the past few sprints). Beware, however, that if you find yourself wanting to ignore the current sprint's effect on velocity often... then you might be over-estimating your velocity.