We heard that in Albania we may have some problems to cross it.
Hallo,
we crossed Albania last year and did´t have any problem. You have to pay 10 € as a entry-fee at the border and that´s it.
Albania is beautiful country unless you don´t stay at the seaside in the North (Durres), which is rather ugly.
The roads are quite rough (even those that -according to your map - are supposed to be "main roads", so a mountain-bike might be the vehicle of ypor choice.
Greetings Nat