Apple Inc. calls interfaces “protocols.” When they say “protocol oriented” they mean programming using interfaces instead of inheritance.

From here: http://www.tutorialspoint.com/objective_c/objective_c_protocols.htm

Objective-C allows you to define protocols, which declare the methods
expected to be used for a particular situation. Protocols are
implemented in the classes conforming to the protocol.

From Objective-C Succintly:

In Objective-C, a protocol is a group of methods that can be
implemented by any class. Protocols are essentially the same as
interfaces in C#, and they both have similar goals. They can be used
as a pseudo-data type, which is useful for making sure that a
dynamically-typed object can respond to a certain set of messages.
And, because any class can “adopt” a protocol, they can be used to
represent a shared API between completely unrelated classes.

From Objective-C for Absolute Beginners:

Apple defines a protocol simply as a list of methods declarations,
unattached to a class definition. The methods listed for protocols are
suppose to be implemented by you.

So, protocol oriented programming is what Objective-C and Swift programmers call what the rest of us call favoring implementing interfaces over extending classes (inheritance).

Is it a new programming paradigm that has the potential to be as
revolutionary as structured programming and abolish the dangerous
“goto” of OOP?

No. It’s nothing new, just a different name used in the Apple developer community. Composition over inheritance has tremendous advantages though that have been discussed extensively in this forum.

And since nothing is ever a silver bullet, what are the pitfalls of
POP?

At first none came to my mind, but I just found this in a forum in CodeRanch, postes by user Jim Yingst:

One disadvantage of interfaces is that one you publish them to other
coders outside your own control, they represent a public commitment
which can be difficult to change later. You don’t know who else is
using the interface and you don’t know how, so you can’t just add a
new method to the interface without risking breaking the code of
existing clients (if/when they upgrade). In comparison, if you’d used
an abstract or concrete class, you could just add a new concrete
method with no problems (usually).

It’s possible to work around this by creating a new interface with
extends or supplements the original one, and changing your concrete
implementations to implement the new interface, instead of or in
addition to the old one. That way you don’t break existing client
code. It’s generally more work than adding a method to a class would
be, but it’s possible.

This disadvantage isn’t a reason to abandon interfaces, but it is a
reason to design your interfaces carefully, and think carefully before
you publish a new interface in a new release. Spending some extra time
designing things well now can save you many headaches later.

On big difference between a Swift/Objective-C protocol and a Java-like interface is that the methods in the former can have default implementations. That’s not something you can do with a Java Interface. It’s almost like having C++ abstract classes and multiple inheritance.

Is POP new? As mentioned already, Objective-C has protocols too, so calling it a “new thing” is a little bit of a stretch. However, what is new to Swift is the ability to implement these protocols using value types rather than reference types and thats the big deal that was featured in Apple’s presentation where POP was introduced.

I did not know the term, being from the Microsoft world. But having read Tulains’s excellent answer I can cover the pitfalls part.

It is not like POP (interfaces) are better than OOP (inheritance), they both have their purposes and strengths. An interface is looser and more flexible. Inheritence ties you to the trunc of a particular class tree but it offers you free implementations of the basics, structure and guidance. If inheritance is done well, it is hard for the subclassing programmer to screw things up.

But the most important reason for the rise of POP is probably the relatively new, distributed, networked world with many developers, that do not know each other, potentially working on the same project. It fits the model of a developing community and it can cross process and/or programming language bounderies (SOA). Inheritance is meaningful only within a single project compiled by the same compiler. Which does not invalidate it, it just has a different domain.

If you don’t care for OOP and think it’s all about inheritance and runtime polymorphism, it may sound reasonable to coin a new term for using protocols for the same purpose.

In my opinion, it is not a useful name and just confuses people about OOP, suggesting that its core tenets are inheritance and runtime polymorphism, as did every beginners’ introduction in a C++ book in the early 1990s.

My suggestion is therefore to avoid the term entirely.