EDIT: Wait, sorry, this counts full binary trees where left and right children are indistinguishable. I suppose this isn't what you want, is it?
Not too hard to fix, fortunately, since the nodes are already labeled: just decide for each internal node whether the child with the higher label is on the right or left. There are 2n ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b1c1b2c2...bn-1cn-1bncn. (There are, of course, (2n)! of these). Given such an anagram, get a binary tree as follows:
First, chop off the last letter, treat the cis as bis, and find the tree with this new string as its Prüfer code. Choose the letter you chopped off to be the root, so every internal node now has two children. To decide which is on the left and which is on the right, ask whether bi came before ci in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.