Estimation and simple math.
Let vOld = old velocity
Let bOld = effort of old baseline
Let bNew = effort of new baseline
Let vNew = new velocity
vNew = vOld * bOld / bNew
Note that if measuring in new points, bNew = 1. Therefore:
vNew = vOld * bOld
For example. Let's say your old velocity is 50 points/sprint.
Let's also say your Team estimates your old baseline story to be worth 2.5 story points using your new definition of points.
Thus, your new velocity is 50 * 2.5 = 125 points/Sprint.
The trick will be accurately and precisely estimating bOld in new points. Note, however, that assuming that the conditions are similar (same developer worked on both stories, no obvious modifiers to performance like interruptions, sleep deprivation, no large gain from improved knowledge etc.), then this estimation will be relatively easy, as all you need to do is look at the difference between the actual time both stories took. For example, if bOld took 5 mandays and bNew took 3, then bOld is 0.6). You should therefore try to pick stories that had as similar conditions as possible.