Generating Ulam numbers with OpenMP and single-thread versions
My CPU is an AMD E1 2500


That CPU is a dual core CPU, so with perfect multithreading that introduces exactly zero overhead, which at best could double the performance. As the comments already pointed out, the overhead is more than zero. Other than that, your CPU is a Kabini low power CPU with 15W TDP, so it's not unlikely that thermal throttling lowers the clock speed when running multithreaded - try to look at the actual clock speed (not % use of CPU) when running the test again. 

With that out of the way, the problem in your code is that you introduce absolutely massive overhead. In addition to the overhead due to having threads, the variable count is shared between threads, which forces the threads to wait for each other all the time. Also, your code will always run the entire loop, while the single-threaded version aborts early. A much faster version is the following, although that one still does not abort early (disclaimer: not tested, as I don't have OpenMP installed).

bool isulam (int n, int size) {
    int count = 0;
    bool toomany = false;
    for (int i = 0; i &lt; size; i++)
        #pragma omp parallel for reduction (+:count)
        for (int j = 0; j &lt; size; j++) {
            if (i != j &amp;&amp; ulam[i]+ulam[j] == n) count++;                
        }
    return count &lt;= 2;
}