Game Not Restarting/Collision Problem

You don't really show the source of the problem, but there are suspect things.

CircToCircCollision uses GetPosition; at the same time, boundary roll-over use AsteroidPosition[i]. How do I know they are the same and AsteroidPosition is updated? There is no indication of AsteroidPosition update. This is inconsistency that should be fixed. You need only one single source of object coordinate data. Then, you should always use a local variable for calculation.

Inside your loop:

var coordinate = asteroid[index].GetPosition();
coordinate.X = //???
asteroid[index].SetPosition(coordinate);

You should not really construct instances of Random over and over inside loop, you should use the same instance.

You need to refactor your code in this way and see it it helps.
Also, your code is greatly spoiled by lack of code re-use and supportability.

We will start talking seriously only if you remove every single innediate constant like 10, 600, 800 (and -- in this context -- even 0). What's going to happen if you need different scene size? You need to everything is a single definition class, or better yet, to a single editable options class.

Coordinate roll-over itself should be made a separate function agnostic to what object is using it:

static Coordinate RollOver(
            Coordinate coodinate,
            Coordinate min, Coordinate max,
            Coordinate size) {
    Coordinate newCoordinate = coodinate;
    //allowed as it works with a copy of parameters:
    min = min - size;
    max = max + size;
    if (coodinate < min)
        coodinate = max;
    else if (coodinate > max)
        coodinate = min;
    return newCoordinate;
} //RollOver

or even in this form:

static void RollOver(
        ref Coordinate coodinate,
        Coordinate min, Coordinate max,
        Coordinate size) {
    min = min - size;
    max = max + size;
    if (coodinate < min)
        coodinate = max;
    else if (coodinate > max)
        coodinate = min;
} //RollOver

I would prefer the second form with ref, because additionally it will prevent using Asteroid property and force you into using a local (hopefully you will use local) variable. Using a property with some side effect could be a source of your particular problem; this form of the method would block the misuse of side effect.

All objects like Asteroid or Spaceship should be well encapsulated without exposing any fields (even via "internal"). GetPosition and SetPosition should be reworked into a single read/write properties. The side effect of property write can be modified inside class to achieve desired effect (such as invalidation of a part of the scene or whatever technique you use). The code using these objects should be made agnostic to these detail.

I'm telling you, even though you do not really show your problem in code: it is solely in data inconsistency (if I can trust your description). If you remove your mess in favor of single-point access to data, you will see that many similar problems will be avoided automatically.

Sorry if your problem is not still resolved. You should understand that your code sample does not show enough to dig out the problem completely and you should not down-vote the answer based on lack of your progress.