POODLE seems to be a padding oracle based on SSL 3.0's inability to fully validate padding. The oracle only gives you the last byte of a block; a full extended padding oracle gives you successive bytes, but this vulnerability doesn't. The authors sidestep that problem by using application-layer control of the boundaries of blocks to repeatedly line up the byte they want to learn with the last byte of padding the vulnerability reveals. C l e v e r !
The difference, I think, between POODLE and BEAST is that BEAST needed not just blockwise "chosen-boundary" control over plaintext, but also a continuous channel that would provide the client with fine-grained control over the first N bytes of each request. It didn't work (IIRC) with vanilla Javascript.
This attack, however, seems to.