Having "magically" found counterexamples, let us explore how we could find at least the first one. Do we really face the specter of having to run thousands of trials? Not if we apply a little ingenuity.
A base 2 palindrome must be odd or else the reverse base 2 representation has an initial zero, not allowed. Then the base 3 representation, being odd, must have an odd sum of digits (c.f. the base 10 test for a multiple of 3). The only base-3 palindromic representations matching this condition have the form $a1a*$ where $a$ is a base 3 representation with no initial zeroes and $a*$ is obtained by reversing the digits of $a$ ($a*$ keeps any initial zeroes corresponding to the terminal zeroes of $a$). Note that not allowing any initial zeroes in $a$ automatically enables us to dodge multiples of 3.
Let us select $a=110_3$ as an example. Keeping the terminal zero as an initial zero of $a*$ gives $a*=011_3$ and thus the odd base 3 palindrome $1101011_3$.
Now we check whether this is palindromic in base 2. A convenient way to do this is to first convert to base 4. Treat the base 3 representation as a polynomial in which the digits, including zeroes, are successive coefficients of decreasing powers of $x$ and evaluate at $x=3$ using synthetic division. In base 4 you use the "multiplication facts" $3×2=12$ and $3×3=21$ to carry out the arithmetic. Applying this technique to $1101011_3$:
$$1=1$$
$$1×3+1=10$$
$$10×3+0=30$$
$$30×3+1=211$$
$$211×3+0=1233$$
$$1233×3+1=11032$$
$$11032×3+1=33223$$
So $1101011_3=33223_4$, and converting each base 4 digit to the appropriate pair of bits then gives $1111101011_2$.
This fails to be a palindrome. A systematic trial would start with $a=1$ and proceed to $a=2, a=10_3$, etc. The first 26 trials fail, on trial 27 the reader can verify that $a=1000_3$ gives, properly, $100010001_3=1213303_4=1100111110011_2$. This is $6643_{10}$.
