I'm trying to get a ESP8266 board with 2x4 pins to work. I'm connecting it to an Olimexino 32u4 (Leonardo-compatible), configured to use 3.3V. This simple snippet I use to transfer everything to the PC (CH_PD is connected to D8, /RST to D9):

void setup() {
 pinMode(8, OUTPUT);
 pinMode(9, OUTPUT);
 digitalWrite(8, LOW);
 digitalWrite(9, LOW);
 delay(2000);
 // initialize both serial ports:
 Serial.begin(9600);
 Serial1.begin(115200);
 delay(10000);
 digitalWrite(9, HIGH);
 digitalWrite(8, HIGH);
}
void loop() {
 // read from port 1, send to port 0:
 if (Serial1.available()) {
 int inByte = Serial1.read();
 Serial.write(inByte);
 }
 // read from port 0, send to port 1:
 if (Serial.available()) {
 int inByte = Serial.read();
 Serial1.write(inByte);
 }
}

When launching, I see following output:

<"random" bytes>
Ai-Thinker Technology Co. Ltd.
invalid

Performing a reset shows more:

AT+RST
OK
 ets Jan 8 2013,rst cause:2, boot mode:(3,6)
load 0x40100000, len 1396, room 16 
tail 4
chksum 0x89
load 0x3ffe8000, len 776, room 4 
tail 4
chksum 0xe8
load 0x3ffe8308, len 540, room 4 
tail 8
chksum 0xc0
csum 0xc0
2nd boot version : 1.4(b1)
 SPI Speed : 40MHz
 SPI Mode : QIO
 SPI Flash Size & Map: 8Mbit(512KB+512KB)
jump to run user1 @ 1000
ŒÂÕ�MEM CHECK FAIL!!!
äsl�‚rô
Ai-Thinker Technology Co. Ltd.
invalid

The mode is set to station:

AT+CWMODE?
+CWMODE:1
OK

Listing the access points works fine:

AT+CWLAP
+CWLAP:(3,"ap-1",-91,"01:23:45:67:89:ab",1)
+CWLAP:(3,"ap-2",-88,"cd:ef:01:23:45:67",2)
+CWLAP:(3,"ap-3",-74,"89:ab:cd:ef:01:23",11)
OK

But logging in to my Fritzbox router fails (WPA2):

AT+CWJAP="ap-2","mypassword"
WIFI CONNECTED
+CWJAP:1
FAIL
WIFI DISCONNECT

First I thought the reason is the low signal, but even moving directly beside the Fritzbox shows the same result (though with higher signal value in AT+CWLAP).

I've tried nearly everything, e.g. AT+CWMODE=3, AT+RST, AT+RESTORE). Nothing changes. When using a wrong password, I'm getting no "WIFI CONNECTED" messages at all.

Could it be a power problem (that the Olimexino can't provide up to 200mA at the 3.3V line?

Connecting from my smartphone to the ESP8266 in one of its access point modes (2 or 3) works fine. If there were power problems, wouldn't then the access point mode fails as well?