I'm no expert, but here goes...
I assume the bottle diameter $d$ is 80 mm, and its glass thickness $l$ is 2 mm. (Height $h$ cancels out of the result). The surface area $A$ of the glass is then approximately $A = \pi d h $.
Start by estimating the thermal conductivities for the 3 heat transfer processes:
Conduction:
The thermal conductivity of glass is $k=1 W/m/K$.
$$q = (k A / l) \Delta T_{glass} = 500 A \Delta T = G_{cond} A \Delta T \quad, \quad G_{cond} = 500 W/m^2/K$$
Convection:
The convective heat transfer coefficient of air is $h=5-25 W/m^2/K$, according to one reference (a lot of wiggle room here):
http://www.engineeringtoolbox.com/convective-heat-transfer-d_430.html
$$ q = h A \Delta T \quad, \quad G_{conv} = h W/m^2/K$$
Radiation (larger than I expected, hat tip to Chris White):
The Stefan-Boltzmann constant is $\sigma = 5.67x10^{-8} W/m^2/K^4$.
$$ q = \epsilon \sigma A \left(T_1^4-T_2^4 \right) = \epsilon \sigma A (T_1^3 + T_1^2 T_2 + T_1 T_2^2 + T_2^3)\Delta T \approx 4 \sigma T_{avg}^3 A \Delta T \approx 5 \epsilon A \Delta T = G_{rad} A \Delta T$$
$$ G_{rad} = 5 \epsilon W/m^2/K$$
Here $\epsilon$ is the emissivity, which is $1$ for a black body and zero for a perfect reflector. Per Schaum's "Heat Transfer" $\epsilon = 0.94$ for smooth glass, which is $1$ at this level of accuracy.
Radiation occurs in parallel with convection, so their conductivities add, while conduction through the glass is in series with the other $2$, so its (relatively very large) conductivity adds in parallel. The total conductivity $G$ is then determined by:
$$q = G A \Delta T$$
$$\frac{1}{G} = \frac{1}{G_{cond}} + \frac{1}{G_{conv}+G_{rad}} \approx \frac{1}{G_{conv}+G_{rad}}$$
$$G \approx 10 - 30 W/m^2/K$$
[Conduction through the glass is much easier than convection + radiation, so the latter two form the heat transfer "bottleneck" (hee hee); conduction is negligibly large.]
Now, for the wine, $q = m C_v dT/dt$ , where $m = \rho V$ , $\rho = 978 kg/m^3 \text{ and } C_v = 4.3 kJ/kg/K$ , according to a report I found on-line:
http://www.gwrdc.com.au/wp-content/uploads/2012/11/WineryB-CaseStudyReport2.pdf
Equating the $2$ expressions for $q$, we get a nice first order diff eq:
$$ \frac{dT}{dt} = (T-T_{amb})/\tau $$
where the time constant $\tau$ is:
$$ \tau = \frac{m C_v}{G A} = \frac{\rho C_v }{G} \frac{V}{A} = \frac{\rho C_v }{G} \frac{d}{4} = \frac{84,100}{G} = 2800-8410 \text{ seconds, or } 47 \text{ to } 140 \text{ minutes}.$$
We're only warming the bottle by $5$ out of the initial temperature difference of $20$ degrees, so we don't need to compute logarithms and instead use a linear expression (equivalent to assuming constant heat flow $q$). The time $t_{warm-up}$ required to achieve optimum serving temperature is just:
$$ t_{warm-up} = \tau \frac{5}{20} = 12 \text{ to } 35 \text{ minutes}.$$
Update:
Here's some data for water in a wine bottle (hey, I'm not wasting good wine). I used one of those vacuum storage stoppers; the hole was just right to poke through a kitchen thermometer. Two diffferent ones, actually. The third curve is an exponential with a 30 minute time constant, which looks to be in the ballpark. It looks like I'm underestimating something, maybe convection?
As everyone else is saying, if you assume Newton's law of cooling:
$$ \dot Q = m c_p \dot T = h A \Delta T $$
The equation for how you heat or cool is an exponential
$$ T(t) = T_\infty + \Delta T e^{ -\frac{hA}{mc_p} t } $$
The rate constant for growth (or dying) of temperature is the same (assuming other details of the material don't change much), so the half-life is the same regardless of the differences in temperatures or goal temperatures, but this does not mean you have to wait the same amount of time. As is the nature of half lives.
I think the best explanation would be a visual one:
Here I'm showing how the temperature would evolve with some made up, yet practical chosen values. If you like, ignore the actual numbers on the scales as they are not that important. What's important is you'll notice that for the red curve I "took it out of the fridge" for 1 hour, and then put it back and it isn't until another 6 hours later that is 41 degrees again. But, for the purple curve, which was out of the fridge long enough to nearly come to room temperature (8 hrs), it takes just as much time to cool down as it took to heat up.
Best Answer
Depends how far you are willing to modify your car. At a simple level, most cars have a "recirculate" switch that draws air from the cabin into the heat exchanger as opposed to heating fresh outside air.
If you want to open the hood, you could blanket the radiator, thus causing the engine coolant to remain rather hotter than planned, which will increase the heat dumped into the cabin air heat exchanger. Similarly, you could muck with the coolant pump's thermostats to force the engine to run hotter. Not recommended if you want your engine to live a long happy life.