I also had 13 years of french instruction and even lived with a francophone girlfriend for several years. I never learned to speak french. On the other hand, I have learned Japanese as an adult without taking any courses.
There are 2 main things to understand. First is that it takes a very long time to learn a language. Many people completely underestimate the task. From the age of 3 years old, humans acquire about 1000 word "families" per year (police, policeman, police truck, policing would all be one word "family". Conjugation (even irregular) is counted in a word family too). This happens up until they are 20. Most university educated adults have more than 25,000 word families in their vocabulary. Even at 5 the average 5 year old has 5,000 word families in their vocabulary.
While you may have been an early developer with language, I think it is likely that your impression of your early abilities is hampering your current development -- mainly because it sets unreasonable expectations. At 6 months old, you may have had a vocabulary of 500-1000 words (it is not unheard of). Most children usually have a vocabulary of 1500 word families by the age of 3 and 5000 by the age of 5.
I recommend talking to 3 year olds and 5 year olds. Their command of their native language is truly awful. And yet, instructors of various languages imply (and sometimes outright say) that their course with 500 words of vocabulary (and a smattering of grammar) will allow you to "learn" the language. Adult level fluency is somewhere on the order of 15,000 word families. Even advanced learners with 7-10K words of vocabulary often can not understand movies without subtitles!
The main problem that people tend to have is that there is a huge disconnect between what they expect to accomplish in a short time frame and what they actually can accomplish. People bandy around ideas like "You can have adult like fluency with 2000 words of vocabulary", but it is absolutely wrong.
Basically, if you learn 20 new words a day (which is not unreasonable with spaced repetition software), you can get to 15K words in 3-5 years but you have to study every single day without a break. More likely is that you can reach that kind of level in about the same time a child can -- 15 years.
Second issue is grammar. There are only about 1500 grammar rules in a typical language. You can rip through them in much less than a year. At this point you will have a fascinating understanding of the language and still be unable to order a drink at a fast food restaurant.
Language acquisition is different than learning (I think this is now the accepted theory, but it's actually a fairly recent development -- in the last 30 years or so). Originally people thought that you memorised language and then practiced it to get faster and faster. Current theory suggests that acquired language springs to mind without pre-planning (we have an associative memory after all). When you are in the correct context (i.e. you want to say something), the correct thing just pops in to your head. Similarly, when you listen to something, understanding occurs without logical analysis. If you have learned language, you are essentially using look up tables and logic to divine the meaning. If you have acquired language, then you go straight from language to meaning (or vice versa).
Studying grammar helps you learn grammar, but does not necessarily help with acquisition. The current accepted theory is that repeated exposure to language that you can understand (usually from context) leads to acquisition.
So what are the practical tips? First, having a course 2-3 times a week will lead to exactly the result you have described: you will not learn the language. You must study every single day (well, my experience has been that 5 days a week will still lead to very slow progress, 4 days will keep you at a standstill and anything less than that will be a treadmill of instantly forgetting what you learned).
Study does not need to be the kind of study you are used to. The absolute best way to learn a language (according to the literature) is free reading. Pick up something you want to read and read it. It should be level appropriate... which is a pain for any language other than English (for which there are about a billion graded readers).
I have found an interesting technique (which I did independently, but later found that it is a very common technique ;-) ). Pick up any book/magazine/whatever that you want to read. Skim it and write down any word you don't know. When you get to 20, look them all up in the dictionary. Use whatever technique you like (spaced repetition software is awesome) to memorise the definitions of the words. Once they are memorised, read the passage again. If you still can't understand it, look up any potential grammar issues in a grammar dictionary. Write down the sentence with the grammar you want to learn along with your own translation of the sentence (after you puzzle it out). Memorise that sentence. Rinse and repeat.
If you are the kind of person who doesn't mind rote work, you can simply memorise all the example sentences in a grammar dictionary (or text book -- although text books suck for the most part). But you still need to do free reading to encounter it in the wild.
For listening, watch TV (or video web sites). For speaking, I have 2 techniques. Read and memorise songs for any genre of music that you like using the technique above. Get recordings of those songs. Sing along. The other technique is to find a news web site that has video news stories as well as a printed version of the story. Read the story. Listen to the story. Then try to read the story at the same time as the news reporter. Try to match pacing, intonation, etc exactly. You can record your voice and compare with the original.
Finally, you need conversation partners. If you live in a large city, you will almost certainly be able to find language meetups in your area. Go and chat with people. Otherwise, there are language exchange websites where you use skype or whatever to chat to people. Being a fluent English speaker will guarantee that you can find as many partners are you like.
Hope that helps! I've had success with these techniques myself, and I have taught them to my students when I was teaching English as a foreign language. I find them very effective. Just temper your expectations and never take a day off. Also realise that courses can never teach you a language because the language is too huge. They best they can do is teach you techniques that will allow you to learn a language. If you are taking a course and it is all about the content, find another course.