System Information
Operating system: Linux-5.0.7-200.fc29.x86_64-x86_64-with-fedora-29-Twenty_Nine 64 Bits
Graphics card: GeForce GTX 980 Ti/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 390.116

Blender Version
Broken: version: 2.80 (sub 57), branch: blender2.7, commit date: 2019-04-15 23:42, hash: rB5ac7675f4c9c (from the buildbot) - also 2.79.6
Worked: I suspect it never worked as documented.

Short description of error
The Python API docs state for ImagePreviewCollection.load and for ImagePreviewCollection.new that is should return "The Preview matching given name, or a new empty one.". In reality it raises an exception when the Preview already exists.

Exact steps for others to reproduce the error
Go to the Python console and type the following.

pcoll = bpy.utils.previews.new()
pcoll.new('test')
pcoll.new('test')  # Error
pcoll.load('test', '', 'IMAGE')  # Error

In the python code a check is done that raises an exception if the Preview already exists (for load there is even a little typo, it should be a format string: f"key {name!r} already exists").
As far as I can see the underlying C code manages existing Previews just fine and has the behavior described in the docs. So I would propose to remove the check from the Python code. Another option would be to properly return the existing Preview from the Python code.
Of course another option would be to change the docs, but personally I would prefer to have the documented behavior.

I've attached 2 patches. 1 for removing the check in the Python code and 1 with the corrected check. The patches should apply to both 2.79 and 2.80.