So what is the difference between Class I and Class II airspace and why should you care? The difference boils down to your proximity to navigational aids and being in one or the other determines your ATC separation standards. While many pilots think it determines your plotting requirements that is not true. See: Navigation / Plotting / When is Plotting Required?.
In 2010, AC 91-70A was updated after thirty years of neglect and added GNSS / GPS to the list of qualified navigation aids to determine Class I airspace, virtually removing all Class II airspace from the globe. I have been told that the chief pilot of a major U.S. airline called the author of the advisory circular who admitted this was a mistake and it would be changed. As of 2015 the mistake remains. So it is up to you, but I do not consider GNSS / GPS reception good enough for Class I airspace.
What follows are quotes from the relevant regulatory documents, listed below, as well as my comments in blue.
[AC 91-70A, ¶10-1.i.] Class I navigation is any en route flight operation conducted in controlled or uncontrolled airspace that is entirely within operational service volumes of ICAO standard NAVAIDs (GNSS, VOR, VOR/DME, and NDB). The operational service volume describes a three-dimensional volume of airspace which categorizes any type of en route navigation as Class I navigation. Within this volume of airspace, IFR navigational performance must be at least as precise as IFR navigation and must use GNSS, VOR, and VOR/DME (or NDB in some countries). The definition of Class I navigation is not dependent upon the equipment installed in the aircraft. En route a VFR flight navigated by pilotage is conducting Class I navigation when operating entirely within the operational service volume. However, the VFR navigational performance in this example must be as precise as VFR pilotage operations are required to be. The operational service volumes of ICAO standard NAVAIDs solely determine the lateral and vertical extent of airspace where you conduct Class I navigation. You cannot conduct Class I navigation outside of this airspace.
(1) VFR or IFR Navigation Operations. Class I navigation also includes VFR or IFR navigation operations on the following:
(2) Separation Minimums. Class I navigation requirements are directly related to separation minimums used by ATC. IFR separation minimums applied in the U.S. National Airspace System (NAS) and most other countries are based on the use of ICAO standard NAVAIDs. ATC, however, can only apply these separation minimums within areas where the NAVAIDs signal in space meets flight inspection signal strength and course quality standards. An ICAO standard NAVAID's signal in space conforms to flight inspection signal strength and course quality standards (including frequency protection) within its designated operational service volume. Therefore, you can predicate air navigation and the safe separation of aircraft within that service volume on the use of these facilities.
(3) Qualifications for Class I Navigation. Within areas where the safe separation of aircraft is based on the use of ICAO standard NAVAIDs, navigate any IFR operation with at least the same precision specified by the appropriate national separation minimums. Any operation or portion of an operation (VFR or IFR) in controlled or uncontrolled airspace with any navigation system (VOR, VOR/DME, NDB, inertial navigation system (INS) and GNSS) is Class I navigation for that portion of the route that is entirely within the operational service volume of ICAO standard en route NAVAIDs.
According to this advisory circular, if you have good GNSS / GPS reception, you are in Class I airspace. I got this email from a reader that sheds some light on this issue:
One of our management pilots talked to the author of this document [AC 91-70], who, when questioned how it's possible for the FAA to define Class I airspace as ground based navaids and then list GNSS as a suitable navaid. The guy said it was a mistake and that he would get it changed. This conversation was in 2010 and it's still unchanged.
[AC 91-70A, ¶10-1.j.] Class II navigation is any en route operation not categorized as Class I navigation and includes any operation, or portion of an operation, that takes place outside the operational service volumes of ICAO standard NAVAIDs. For example, an aircraft equipped with only VOR conducts Class II navigation when the flight operates in an area outside the operational service volumes of federal VORs/DMEs.
(2) Class II Navigation Definition. The definition of Class II navigation is not dependent upon the equipment installed in the aircraft. All airspace outside the operational service volume of ICAO standard NAVAIDs is a three-dimensional volume of airspace within which any type of en route navigation is Class II navigation. For any type of navigation within this volume of airspace, the IFR navigational performance must be as precise as the navigational performance assumed during establishment of the ATC separation minimums for that volume of airspace. The navigational performance for VFR operations in a Class II navigation volume of airspace must be only as precise as VFR navigation operations are required to be.
Figure: Standard High Altitude Service Volumes, from Aeronautical Information Manual, Figure 1-1-1.
You can have a navaid tuned and identified far outside its service volume, which means it doesn't count when making the plot / don't plot decision. Typical service volumes from [Aeronautical Information Manual, ¶1-1-8:
Portions of this page can be found in the book International Flight Operations, Part II, Chapter 4.
Advisory Circular 20-138D, Positioning and Navigation Systems, 5/8/12, U.S. Department of Transportation
Advisory Circular 91-70A, Oceanic and International Operations, 8/12/10, U.S. Department of Transportation