Are they considered "Very Friendly" or just "Friendly"? If just "Friendly", try giving them a state gift (the 1 that is 2500) and then it should goto "Very Friendly" and then request an alliance. That should work.

Although, I am doing it w/o an alliance.